package XPathProj;

import java.io.IOException;
import java.util.AbstractMap;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

import javax.xml.namespace.QName;
import javax.xml.parsers.DocumentBuilder;
import javax.xml.parsers.DocumentBuilderFactory;
import javax.xml.parsers.ParserConfigurationException;
import javax.xml.xpath.XPath;
import javax.xml.xpath.XPathConstants;
import javax.xml.xpath.XPathExpressionException;
import javax.xml.xpath.XPathFactory;

import org.w3c.dom.Document;
import org.w3c.dom.Node;
import org.w3c.dom.NodeList;
import org.xml.sax.SAXException;

public class XPathProjectImplementation extends XPathProject {
	
	// indices in boolean condition token list
	private static final int PREFIX_INDX = 0;
	private static final int OPERATOR_INDX = 1;
	private static final int POSTFIX_INDX = 2;
	
	// numeric values representing boolean condition sampling result
	private static final int EXPRESSION_AT_PREFIX_ONLY = 0;
	private static final int EXPRESSION_AT_POSTFIX_ONLY = 1;
	private static final int EXPRESSION_AT_BOTH_SIDES = 2;
	private static final int NO_EXPRESSION_AT_BOTH_SIDES = 3;
	private static final int SINGLE_TOKEN = 4;
	private static final int ID_AT_PREFIX = 5;
	private static final int ID_AT_POSTFIX = 6;
	private static final int NUMERIC_ERROR_VAL = -1;
	
	private XPath xpath; // used to perform xpath queries
	private Document doc; // xml document to be parsed
	
	/**
	 * Constructor- creates a new object implementing the XPath project
	 */
	public XPathProjectImplementation() {

		// no document has been loaded yet
		doc = null;
		
		// create an XPath Object
		xpath = XPathFactory.newInstance().newXPath();
	}
	
	/**
	 * Builds XML tree according to given file
	 */
	@Override
	public void loadXML(String fileLocation) throws SAXException, IOException,
			IllegalArgumentException {
		
		try {
			
			//load the document into a DOM Document
			DocumentBuilderFactory domFactory = DocumentBuilderFactory.newInstance();
			domFactory.setNamespaceAware(true);
			DocumentBuilder builder;
			builder = domFactory.newDocumentBuilder();
			doc = builder.parse(fileLocation);
			
		} catch (ParserConfigurationException e) {

			// could not parse document
			throw new IOException();
		}
	}

	/**
	 * Evaluates given xpath expression and returns result of
	 * given type
	 */
	@Override
	public Object evaluate(String expression, QName returnType)
			throws XPathExpressionException, IllegalArgumentException,
			NullPointerException {

		// evaluate expression with document as source node		
		return evaluate(expression, doc, returnType);
	}

	/**
	 * Evaluates given xpath expression on given source node. 
	 * Returns result of given type:
	 * NUMBER- returns numeric value of first node in the result nodes list
	 * STRING- returns string value of first node in the result nodes list
	 * BOOLEAN- returns True if given expression results in "true", otherwise returns False
	 * NODE- returns first node in the result nodes list
	 * NODESET- returns results nodes and their paths in a list of type XPathProjectNodeListImplementation.
	 */
	public Object evaluate(String expression, Node source, QName returnType)
			throws XPathExpressionException, IllegalArgumentException,
			NullPointerException {
		
		// confirm validity of return type
		if (!isReturnTypeValid(returnType)) {
			
			// return type is not valid
			throw new IllegalArgumentException();
		}
		
		// check if should return a numeric value
		if (returnType.equals(XPathConstants.NUMBER)) {
			
			// return round parentheses that wrap entire expression
			expression = removeParentheses(expression, '(', ')');
			
			// try splitting by arithmetic operator
			List<String> tokens = splitByArithmeticOperator(expression);
			
			// check if could not split
			if (tokens.isEmpty()) {
				
				// check if expression is a number
				double numericValue = 0;
				try {
					
					// extract number
					numericValue = Double.parseDouble(expression);
					return numericValue;
					
				} catch (NumberFormatException e) {			
				
					// get result nodes according to the expression
					XpathNodeListImplementation result = (XpathNodeListImplementation) evaluateExpression(expression, source);
					
					// check if could get numeric result
					if (result.getLength() == 0) { return Double.NaN; }
					
					// extract numeric value from the result and return it
					Node resultNode = result.item(0);
					numericValue = (double) xpath.evaluate("self::node()", resultNode, XPathConstants.NUMBER);				
					return numericValue;
				}
			}
			
			// could split- evaluate results of prefix and postfix
			
			// get result nodes according to the prefix
			double prefixResult = (double) evaluate(tokens.get(PREFIX_INDX), source, XPathConstants.NUMBER);
			
			// check if could get numeric result for prefix
			if (Double.isNaN(prefixResult)) { return Double.NaN; }
			
			// get result nodes according to the postfix
			double postfixResult = (double) evaluate(tokens.get(POSTFIX_INDX), source, XPathConstants.NUMBER);
			
			// check if could get numeric result for postfix
			if (Double.isNaN(postfixResult)) { return Double.NaN; }
			
			// return final result
			return (double) xpath.evaluate(prefixResult + " " + tokens.get(OPERATOR_INDX) + " " + postfixResult, doc, XPathConstants.NUMBER);
		}
		
		if (returnType.equals(XPathConstants.STRING)) {
		
			// get result nodes of given expression
			XpathNodeListImplementation result = (XpathNodeListImplementation) evaluateExpression(expression, source);
			
			// check if could get any nodes 
			if (result.getLength() == 0) { return ""; }
			
			// get first node on result list
			Node resultNode = result.item(0);
			
			// extract node's string value
			String string = (String) xpath.evaluate("self::node()", resultNode, XPathConstants.STRING);
			
			// return node's string value
			return string;
		}
		
		if (returnType.equals(XPathConstants.BOOLEAN)) {
			
			// get validation for given expression
			String validation = validateBooleanCondition(expression, source, 0);
			
			// return True if could validate expression
			return !validation.equals("");
		}
		
		if (returnType.equals(XPathConstants.NODE)) {
			
			// evaluate expression and get nodes in correct order and their paths
			XpathNodeListImplementation result = (XpathNodeListImplementation) evaluateExpression(expression, source);
			
			// return first item on list
			return result.item(0);
		}
		
		// evaluate expression and get nodes in correct order and their paths
		XpathNodeListImplementation result = (XpathNodeListImplementation) evaluateExpression(expression, source);
		
		// return result list
		return result;
	}

	/*
	 * "Algorithmic" methods- used to perform the logics of the evaluation 
	 * and path-finding process
	 */
	
	/**
 	 * Evaluates given expression on source node. Return the nodes that fulfill the expression requirements
 	 * and the validation (path) for the nodes.
 	 * The expression is divided to subexpressions: divides the expression according to instances of "|" that
 	 * are not between parentheses.
 	 * Each subexpression is divided to segments: divides the subexpression according to instances of "/" that
 	 * are not between parentheses.
 	 * For each subexpression, the first segment is evaluated on the source node, the second segment is evaluated on
 	 * the result nodes and so on.
 	 * The result nodes of each subexpression, and the nodes' validations, are returned- but duplicate nodes
 	 * are not allowed
 	 * @param expression- expression to be evaluated
 	 * @param source- source node for the evaluation
 	 * @return nodes that fulfill the expression requirements and the proof for the nodes
 	 * @throws XPathExpressionException if condition's syntax is incorrect
 	 */
	private Object evaluateExpression(String expression, Node source) throws XPathExpressionException {
			
		// check if source node was specified
		if (null == source) {
			
			// start from root
			source = (Node) xpath.evaluate("self::node()", doc, XPathConstants.NODE);
		}

		// replace axis abbreviations with the axis itself
		expression = replaceAbbrvWithAxis(expression);
		
		// initialize source nodes list
		XpathNodeListImplementation sources = new XpathNodeListImplementation();
		
		// holds results of all sub expressions
		XpathNodeListImplementation results = new XpathNodeListImplementation();
		
		// split to sub expressions
		List<String> subExpressions = splitExpressions(expression, '|');
		
		// evaluate each sub expression
		for (String currExp : subExpressions) {
							
			// split current sub expression to segments 
			List<String> segments = splitExpressions(currExp, '/');				

			// clear source nodes list from previous iteration
			sources.clear();
			
			// initialize sources list with given source (no id() is in an empty expression)
			addNodes(new LinkedList<String>(), (NodeList) xpath.evaluate(
					"self::node()", source, XPathConstants.NODESET), sources,
					"", "", "", false, true, source, false);
			
			// evaluate each segment
			for (String currSegment : segments) {
		
				// get nodes of current segment's result
				sources = getNodesOfSegment(currSegment, sources);
			}
			
			// accumulate current sub expresssion's result
			results.addNodeList(sources);
		}
		
		// return results of all sub expressions
		return results;
	}

	/**
	 * Evaluates given expression's segment on source nodes and returns the nodes
	 * that fulfill the segment's requirements and their validations.
	 * If given segment is between round parentheses, evaluates entire expression
	 * inside parentheses, and then checks the conditions
	 * @param segment- segment of the expression to be evaluated
	 * @param sources- source nodes that the segment should be evaluated on
	 * @return nodes that fulfill the segment's requirements and their proofs
	 * @throws XPathExpressionException if condition's syntax is incorrect
	 */
	private XpathNodeListImplementation getNodesOfSegment(String segment,
			XpathNodeListImplementation sources) throws XPathExpressionException {
		
		// holds result of current segment
		XpathNodeListImplementation currSegmentResult = new XpathNodeListImplementation();
		
		// remove condition from given segment
		String segmentWithoutCondition = getExpressionWithoutCondition(segment);
		String condition = extractCondition(segment);

		// check if segment is bounded between round parentheses
		if (isExprBetweenRoundParentheses(getExpressionWithoutCondition(segment))) {
			
			// remove round parentheses from segment
			String segmentNoParen = removeParentheses(getExpressionWithoutCondition(segment), '(', ')');
			
			// evaluate segment for each source node
			int numOfSources = sources.getLength();
			for (int i = 0 ; i < numOfSources ; ++i) {

				// result nodes for current source node
				XpathNodeListImplementation currSourceResults = new XpathNodeListImplementation();
				
				// get candidate nodes for current source node
				XpathNodeListImplementation candidateNodes = (XpathNodeListImplementation) evaluate(segmentNoParen, sources.item(i), XPathConstants.NODESET);

				// if no candidates found, move to next source node
				if (candidateNodes.getLength() == 0) { continue; }
				
				// add back the round parentheses with node's index
				int numOfCandidates = candidateNodes.getLength();
				for (int j = 0 ; j < numOfCandidates ; ++j) {
					
					// avoid adding index if there is only a single candidate
					if (numOfCandidates == 1) {
						candidateNodes.setItemPath("("  +candidateNodes.itemPath(j) + ")", j);
						continue;
					}
					
					// multiple candidates, add index
					candidateNodes.setItemPath("("  +candidateNodes.itemPath(j) + "){" + (j+1) + "}", j);
				}
				
				// add candidate nodes that fulfill the condition
				addNodesWrapper(candidateNodes.getPathList(), candidateNodes,
						currSourceResults, condition,
						sources.itemPath(i) + "/", true, sources.item(i));
				
				// add current source's results to segment's result list
				currSegmentResult.addNodeList(currSourceResults);
			}
			
			// return current segment's result nodes
			return currSegmentResult;
		}
		
		// perform expression's segment on each source node
		int numOfSourcesNodes = sources.getLength();
		for (int i = 0 ; i < numOfSourcesNodes ; ++i) {
			
			// result nodes for current source node
			XpathNodeListImplementation currSourceResults = new XpathNodeListImplementation();
			
			// get candidate nodes for the condition according to current source node
			NodeList candidateNodes = (NodeList) xpath.evaluate(segmentWithoutCondition, sources.item(i), XPathConstants.NODESET);

			// if candidates found, move to next source node
			if (candidateNodes.getLength() == 0) { continue; }
			
			// add candidate nodes that fulfill the condition
			addNodesWrapper(new LinkedList<String>(), candidateNodes, currSourceResults, segment, sources.itemPath(i) + "/", false, sources.item(i));
			
			// add current source's results to segment's result list
			currSegmentResult.addNodeList(currSourceResults);
		}
		
		// return current segment's result nodes 
		return currSegmentResult;
	}
	
	/**
	 * Adds given candidate nodes to result list. 
	 * "Wraps" the node-adding by firstly extracting the conditions and evaluate each condition on the result 
	 * of the previous condition. Uses the method addNodes() to add nodes that fulfill current condition being 
	 * scanned among successive conditions. Successive conditions are for example: 
	 * "/inventory/book[condition_1][condition_2]...[condition_n] 
	 * @param candidateValidations- list holding validation for each candidate node
	 * @param candidateNodes- list holding candidate nodes
	 * @param results- output parameter, will hold nodes that fulfill the expression and their validations
	 * @param expression- xpath expression from evaluation's source node. Used to choose the suitable candidates
	 * @param prevPath- path to evaliation's source node
	 * @param usePrevPath- indicates if should use previous path when composing the path for candidate node being
	 * 					   added to results list
	 * @param source- evaluation's source node
	 * @throws XPathExpressionException if had problems adding candidate nodes to result list
	 */
	private void addNodesWrapper(List<String> candidateValidations,
			NodeList candidateNodes, XpathNodeListImplementation results,
			String expression, String prevPath, boolean usePrevPath, Node source)
			throws XPathExpressionException {
        
        // extract the condition
        List<String> successiveConditions = extractSuccessiveConditions(extractCondition(expression));
        
        // get numbers of successive conditions
        int numOfConditions = successiveConditions.size();
        
        // check if expression contains a condition
        if (numOfConditions == 0) {
        	
        	// add the nodes according to the expression, no need to check the index among candidates
        	// add id() parameter (if exists)
        	addNodes(candidateValidations, candidateNodes, results, expression, "", prevPath, false, usePrevPath, source, true);
        	return;
        }

    	// add nodes that fulfill first condition, add id() parameter (if exists)
    	addNodes(candidateValidations, candidateNodes, results, expression, successiveConditions.get(0), prevPath, true, usePrevPath, source, true); 

    	
    	// if no nodes fulfill the first condition, no need to check other conditions    	
        if (results.getLength() == 0) { return; }
        
        // set results of first condition as candidates for the next condition
        XpathNodeListImplementation currCandidates = new XpathNodeListImplementation(results);
        
        // initialize results list
        XpathNodeListImplementation currResults = new XpathNodeListImplementation();
        
        // evaluate each condition on remained node set
        boolean hasMoreConditions = false; // indicates if there are any more conditions to evaluate
        for (int i = 1 ; i < numOfConditions ; ++i) {
        	
        	// multiple conditions
        	hasMoreConditions = true;
        	
        	// save the results of current evaluation only
        	currResults.clear();

        	// add nodes and check candidate's index, no need to add id() parameter
			addNodes(currCandidates.getPathList(), currCandidates,
					currResults, expression, successiveConditions.get(i),
					prevPath, true, usePrevPath, source, false); 

        	// use current results as candidates for the next evaluation
        	currCandidates.clear();
        	currCandidates.addNodeList(currResults);
        }
        
        // check if should update the final result
        if (hasMoreConditions) {
        	
        	// only results of last evaluation will be the final result
        	results.clear();
        	results.addNodeList(currResults);
        }
	}
	
	/** 
	 * Adds given nodes to the node list, according to the XPath expression that had retrieved the nodes-
	 * if the expression has reverse axes, nodes are added in reversed order.
	 * Otherwise, nodes are added normally
	 * If a condition is specified, adds only the nodes that fulfill the condition
	 * @param candidateValidations- list holding validation (path made) for each candidate node
	 * @param candidateNodes- candidate nodes that need to be checked if fulfill the condition
	 * @param results- node list to which the nodes will be added  
	 * @param expression- XPath expression that retrieved the nodes
	 * @param condition- condition that candidate node should fulfill in order to be added to
	 * 					 result list
	 * @param prevPath- path to evaliation's source node
	 * @param checkIndex- if condition is a numeric value, indicates if should add candidate at this position
	 * 					  or ignoring the condition and add candidates anyway 
	 * @param usePrevPath- indicates if should use previous path when composing the path for candidate node being
	 * 					   added to results list
	 * @param source- evaluation's source node
	 * @param addID- indicates if should add id()'s parameter (if exists) to the path of node being added to result list 
	 * @throws XPathExpressionException if had problems adding candidate nodes to result list
	 */
	private void addNodes(List<String> candidatesValidations,
			NodeList candidateNodes, XpathNodeListImplementation results,
			String expression, String condition, String prevPath,
			boolean checkIndex, boolean usePrevPath, Node source, boolean addID) throws XPathExpressionException {
		
		// remove condition from expression
		String exprWithoutCondition = getExpressionWithoutCondition(expression);
		
		// get number of possible nodes to add
		int numOfCandidates = candidateNodes.getLength();
		
		// check if should reverse node order
		if (hasReverseAxes(expression)) {

			// check if condition is "last()" or "last()" between round parentheses
			if (isConditionLast(condition)) {
				
				// build path for last candidate node (iterating in revered order, therefore last node is position 0 on list)
				String path = composeNodePath(candidatesValidations, prevPath,
						exprWithoutCondition, numOfCandidates - 1, "[last()]",
						numOfCandidates, usePrevPath, source,
						candidateNodes.item(0), addID);
				
				// add the last candidate node to the results list
				results.addNode(new AbstractMap.SimpleEntry<Node, String>(candidateNodes.item(0), path));

				// no need to add other nodes
				return;
			}
			
			// add nodes in reverse order
			for (int i = numOfCandidates - 1; i >= 0; --i) {

				// check if condition is "not(last())"
				if (isConditionNegativeLast(condition)) {
					
					// add current node if it is not the last one
					if (i != 0) { // last one is position 0 since iterating in reversed order
						
						// build path for current candidate node
						String path = composeNodePath(candidatesValidations,
								prevPath, exprWithoutCondition, numOfCandidates	- i - 1, 
								"[not(last())]", numOfCandidates, usePrevPath, source,
								candidateNodes.item(i), addID);
						
						// add current node to the results list
						results.addNode(new AbstractMap.SimpleEntry<Node, String>(candidateNodes.item(i), path));
						
					} else { continue; }
				}				
				
				String conditionValidator = "";
				String currNodePath = "";

				// check if expression contains a condition
				if (!condition.equals("")) {

					// get path to first proof of condition's validity
					conditionValidator = validateBooleanCondition(condition, candidateNodes.item(i), i+1);

					// check if could validate condition
					if (conditionValidator.equals("")) {

						// check if given condition only specifies an index
						int index = getIndexCondition(condition, i+1, candidateNodes.item(i)); 
						
						/*
						 * add index'th candidate only if should check that candidate's index matches condition's numeric value,
						 * otherwise add current candidate
						 */ 
						if ((!checkIndex && index != -1) || checkIndex && index == (numOfCandidates-i)) { 

							// compose index validation
							conditionValidator = condition;

							// compose current node's path
							currNodePath = composeNodePath(
									candidatesValidations, prevPath,
									exprWithoutCondition, numOfCandidates - i - 1, 
									conditionValidator, numOfCandidates, usePrevPath, source,
									candidateNodes.item(i), addID);
														
							// and current node and its path
							results.addNode(new AbstractMap.SimpleEntry<Node, String>(candidateNodes.item(i), currNodePath));

							// move to next node
							continue;

						} else {

							// current node does not fulfill condition
							continue;
						}

					}
				}

				// compose current node's path
				currNodePath = composeNodePath(candidatesValidations, prevPath,
						exprWithoutCondition, numOfCandidates - i - 1,
						conditionValidator, numOfCandidates, usePrevPath,
						source, candidateNodes.item(i), addID);

				// and current node and its path
				results.addNode(new AbstractMap.SimpleEntry<Node, String>(candidateNodes.item(i), currNodePath));
			}

		} else {

			// check if condition is "last()" or "last()" between round parentheses
			if (isConditionLast(condition)) {
				
				// build path for last candidate node
				String path = composeNodePath(candidatesValidations, prevPath,
						exprWithoutCondition, numOfCandidates - 1, "[last()]",
						numOfCandidates, usePrevPath, source,
						candidateNodes.item(numOfCandidates - 1), addID);
				
				// add the last candidate node to the results list
				results.addNode(new AbstractMap.SimpleEntry<Node, String>(candidateNodes.item(numOfCandidates - 1), path));

				// no need to add other nodes
				return;
			}
			
			// add nodes normally
			for (int i = 0; i < numOfCandidates; ++i) {
				
				// check if condition is "not(last())"
				if (isConditionNegativeLast(condition)) {
					
					// add current node if it is not the last one
					if (i != numOfCandidates - 1) {
						
						// build path for current candidate node
						String path = composeNodePath(candidatesValidations,
								prevPath, exprWithoutCondition, i,
								"[not(last())]", numOfCandidates, usePrevPath,
								source, candidateNodes.item(i), addID);
						
						// add current node to the results list
						results.addNode(new AbstractMap.SimpleEntry<Node, String>(candidateNodes.item(i), path));
						
					} else { continue; }
				}
								
				String conditionValidator = "";
				String currNodePath = "";

				// check if expression contains a condition
				if (!condition.equals("")) {
					
					// get path to first proof of condition's validity
					conditionValidator = validateBooleanCondition(condition, candidateNodes.item(i), i+1);

					// check if could validate condition
					if (conditionValidator.equals("")) {

						// check if given condition only specifies an index
						int index = getIndexCondition(condition, i+1, candidateNodes.item(i));
						
						/*
						 * add index'th candidate only if should check that candidate's index matches condition's numeric value,
						 * otherwise add current candidate
						 */ 
						if ((!checkIndex && index != -1) || checkIndex && index == (i + 1)) {

							// compose index validation
							conditionValidator = condition;

							// compose current node's path
							currNodePath = composeNodePath(
									candidatesValidations, prevPath,
									exprWithoutCondition, i,
									conditionValidator, numOfCandidates,
									usePrevPath, source,
									candidateNodes.item(i), addID);

							// and current node and its path
							results.addNode(new AbstractMap.SimpleEntry<Node, String>(candidateNodes.item(i), currNodePath));

							// move to next node
							continue;

						} else {

							// current node does not fulfill condition
							continue;
						}

					}
				}

				// compose current node's path				
				currNodePath = composeNodePath(candidatesValidations, prevPath,
						exprWithoutCondition, i, conditionValidator,
						numOfCandidates, usePrevPath, source,
						candidateNodes.item(i), addID);

				// and current node and its path
				results.addNode(new AbstractMap.SimpleEntry<Node, String>(candidateNodes.item(i), currNodePath));
			}
		}
	}
	
	/**
	 * Finds validation (proof) for given boolean condition:
	 * Gets all candidate nodes that could fulfill the condition, using evaluate method.
	 * Gets all nodes that fulfill the condition using the xpath object.
	 * Finds first match between candidate and node that fulfills the condition.
	 * The validation is composed using the path claimed from the evaluate method and
	 * the index of the matching candidate node 
	 * @param condition- boolean condition to be validated
	 * @param candidate- candidate node to be added (source node for test evaluations)
	 * @param candidateIndex- index of candidate node 
	 * @return if exists- validation for the boolean condition, otherwise- returns an empty string
	 */
	private String validateBooleanCondition(String condition, Node candidate, int candidateIndex) {
		
		// check if given condition only specifies an index
		if (!condition.equals("") && !isNotSimpleIndexCondition(condition)) {
			
			// no need to validate
			return "";
		}		
		
		// remove predicate parentheses
		condition = removeParentheses(condition, '[', ']');
		
		// remove round parentheses
		condition = removeParentheses(condition, '(', ')');
		
		// check if condition is composed of "|"
		if (splitExpressions(condition, '|').size() > 1) { return validateConditionWithPipe(condition, candidate, candidateIndex); }
		
		// check if condition is composed of "and"
		if (!splitBooleanConditionByString(condition, "and").isEmpty()) { return validateConditionWithAnd(condition, candidate, candidateIndex); }
		
		// check if condition is composed of "or"
		if (!splitBooleanConditionByString(condition, "or").isEmpty()) { return validateConditionWithOr(condition, candidate, candidateIndex); }
		
		// check if condition is negative ( not(...) )
		if (isNegativeCondition(condition)) { return validateNegativeCondition(condition, candidate, candidateIndex); }
		
		// split expression according to free instance of the operator
		List<String> conditionTokens = splitBooleanConditionByOperator(condition);

		// replace axis abbreviations in each token
		replaceAxisAbrvInTokens(conditionTokens);

		// remove round parentheses from prefix
		boolean addParenToPrefix = false, addParenToPostfix = false;
		if (!conditionTokens.isEmpty()) {
			
			// check if should add back the round parentheses after the validation
			addParenToPrefix = processTokenParentheses(conditionTokens, PREFIX_INDX);
			addParenToPostfix = processTokenParentheses(conditionTokens, POSTFIX_INDX);
		}
		
		// sample the condition according to its tokens
		int expressionType = sampleBooleanCondition(conditionTokens);
		
		// lists to hold candidate nodes and nodes that fulfill the condition
		XpathNodeListImplementation candidateNodes = null;
		NodeList fulfillingNodes = null;
		
		String beforeOperator = null;
		
		// indicates if should place the path-proof at the postfix
		boolean isProofAtPostfix = false;
			
		try {
			
			// find condition validation according to sampling result 
			switch (expressionType) {
			case EXPRESSION_AT_PREFIX_ONLY: {
				
				// get the expression before the operator
				beforeOperator = conditionTokens.get(PREFIX_INDX);

				// compose expression to get nodes that fulfill the condition
				String fulfillingNodesExpression = composeFulfillingNodesExpression(
						conditionTokens.get(PREFIX_INDX),
						conditionTokens.get(OPERATOR_INDX),
						conditionTokens.get(POSTFIX_INDX), false, false);
				
				// get all nodes that fulfill the condition	
				fulfillingNodes = (NodeList) xpath.evaluate(fulfillingNodesExpression, candidate, XPathConstants.NODESET);
				
				break;
			}

			case EXPRESSION_AT_POSTFIX_ONLY: {
				
				// get the expression before the operator
				beforeOperator = conditionTokens.get(POSTFIX_INDX);

				// compose expression to get nodes that fulfill the condition
				String fulfillingNodesExpression = composeFulfillingNodesExpression(
						conditionTokens.get(POSTFIX_INDX),
						conditionTokens.get(OPERATOR_INDX),
						conditionTokens.get(PREFIX_INDX), false, true);
				
				// get all nodes that fulfill the condition
				fulfillingNodes = (NodeList) xpath.evaluate(fulfillingNodesExpression, candidate, XPathConstants.NODESET);
								
				// swap prefix and postfix in condition's validation
				isProofAtPostfix = true;
				
				break;
			}
			
			case EXPRESSION_AT_BOTH_SIDES: {
				
				// validate the condition considering expressions at both sides of operator
				return handleConditionAtBothSides(conditionTokens, candidate, false, addParenToPrefix, addParenToPostfix);
			}
				
			case NO_EXPRESSION_AT_BOTH_SIDES: {
				
				// does not have to provide a validation to condition using a path
				return handleNoExpressionNearOperator(conditionTokens, candidate, false, candidateIndex);
			}
				
			case SINGLE_TOKEN: {
				
				// check if should start evaluation from document root
				if (condition.charAt(0) == '/') { candidate = doc; }

				// check if condition is atomic
				if (condition.startsWith("true(") || condition.startsWith("false(")) {
					return handleAtomicCondition(condition, candidate);
				}

				// validate the condition
				return validateConditionNoBooleanOperator(condition, candidate);
			}

			case ID_AT_PREFIX: {

				// split prefix to segments
				List<String> prefixSegments = splitExpressions(conditionTokens.get(PREFIX_INDX), '/');
				
				// compose expression to get relevant nodes
				String fulfillingNodesExpression = prefixSegments.get(0) + "[" 
												   + conditionTokens.get(PREFIX_INDX).substring(prefixSegments.get(0).length()+1) 
												   + conditionTokens.get(OPERATOR_INDX) 
												   + conditionTokens.get(POSTFIX_INDX) + "]";

				// get fulfilling nodes
				fulfillingNodes = (NodeList) xpath.evaluate(fulfillingNodesExpression, candidate, XPathConstants.NODESET);
				
				// get candidate nodes
				String candidatesExpression = prefixSegments.get(0);
				XpathNodeListImplementation candidates = (XpathNodeListImplementation) evaluate(candidatesExpression, candidate, XPathConstants.NODESET);
				
				// get nodes resulting from expression at prefix
				XpathNodeListImplementation prefixNodes = (XpathNodeListImplementation) evaluate(conditionTokens.get(PREFIX_INDX), candidate, XPathConstants.NODESET);
				
				// return validation for the entire condition
				return handleIDAtOneSide(conditionTokens,
						prefixNodes.getPathList(), candidates, fulfillingNodes,
						false, false, addParenToPrefix, addParenToPostfix);
			}
			
			case ID_AT_POSTFIX: {
			
				// split postfix to segments
				List<String> postfixSegments = splitExpressions(conditionTokens.get(POSTFIX_INDX), '/');

				// compose expression to get relevant nodes
				String fulfillingNodesExpression = postfixSegments.get(0) + "[" 
												   + conditionTokens.get(PREFIX_INDX) 
												   + conditionTokens.get(OPERATOR_INDX) 
												   + conditionTokens.get(POSTFIX_INDX).substring(postfixSegments.get(0).length()+1) + "]";
				
				// get fulfilling nodes
				fulfillingNodes = (NodeList) xpath.evaluate(fulfillingNodesExpression, candidate, XPathConstants.NODESET);
				
				// get candidate nodes
				String candidatesExpression = postfixSegments.get(0);
				XpathNodeListImplementation candidates = (XpathNodeListImplementation) evaluate(candidatesExpression, candidate, XPathConstants.NODESET);
				
				// get nodes resulting from expression at postfix
				XpathNodeListImplementation postfixNodes = (XpathNodeListImplementation) evaluate(conditionTokens.get(POSTFIX_INDX), candidate, XPathConstants.NODESET);
				
				// return validation for the entire condition
				return handleIDAtOneSide(conditionTokens,
						postfixNodes.getPathList(), candidates,
						fulfillingNodes, true, false, addParenToPrefix,
						addParenToPostfix);
			}
			
			default:
				break;
			}
			
			// get candidates for condition with expression at only one side of the operator
			candidateNodes = getCandidateNodes(beforeOperator, candidate);
			
			// handle a non-negative expression at only one side of the operator
			return handleExpressionAtOneSide(conditionTokens, beforeOperator,
					candidateNodes, fulfillingNodes, isProofAtPostfix, false,
					addParenToPrefix, addParenToPostfix);

		} catch (XPathExpressionException e1) {

			// no validation			
			return "";
			
		} catch (IllegalArgumentException e1) {

			// no validation
			return "";
			
		} catch (NullPointerException e1) {

			// no validation
			return "";
		}
	}
	
	/**
	 * Splits given condition by free instances of "|" and evaluates each sub condition separately.
	 * Since this condition is fulfilled if expression results in a non-empty node set,
	 * condition is validated if at least one sub condition could be validated.
	 * Condition validation will be the validation of the first sub condition that can be validated
	 * @param condition- condition to be evaluated
	 * @param source- source node for the evaluation
	 * @return if exists- validation for the condition, otherwise- returns an empty string
	 */
	private String validateConditionWithPipe(String condition, Node source, int candidateIndex) {
		
		// split condition by free instances of "|"
		List<String> subConditions = splitExpressions(condition, '|');
		
		// try validating each sub condition
		int numOfSubConditions = subConditions.size();
		for (int i = 0 ; i < numOfSubConditions ; ++i) {
			
			// get validation of current sub condition
			String currSubCondValidation = validateBooleanCondition(subConditions.get(i), source, candidateIndex);
			
			// check if could validate
			if (currSubCondValidation.equals("")) {
				
				// try validating next sub condition
				continue;
				
			} else {
				
				// return condition validation
				return currSubCondValidation;
			}
		}
		
		// could not validate condition
		return "";
	}
	
	/**
	 * Handles condition with "and", where "and"'s instance not between parentheses (free):
	 * verifies that both parts can be validated
	 * @param condition- condition to be validated
	 * @param source- source node for the evaluation
	 * @param candidateIndex- index of candidate node among other candidates (counts from 1)
	 * @return if exists- validation for the condition, otherwise- returns an empty string
	 */
	private String validateConditionWithAnd(String condition, Node source, int candidateIndex) {

		// split condition by "and"
		List<String> conditionTokens = splitBooleanConditionByString(condition, "and");

		// check if prefix is between round parentheses
		boolean addParenthesesToPrefix = processTokenParentheses(conditionTokens, PREFIX_INDX);
		
		// validate prefix
		String prefixValidation = validateBooleanCondition(conditionTokens.get(PREFIX_INDX), source, candidateIndex);
		
		// check if postfix is between round parentheses
		boolean addParenthesesToPostfix = processTokenParentheses(conditionTokens, POSTFIX_INDX);
		
		// validate postfix
		String postfixValidation = validateBooleanCondition(conditionTokens.get(POSTFIX_INDX), source, candidateIndex);
		
		// check if both parts of condition are fulfilled
		if (prefixValidation.equals("") || postfixValidation.equals("")) {
			
			// at least one part is not fulfilled
			return "";
		}
		
		// remove predicate parentheses from both parts
		prefixValidation = removeParentheses(prefixValidation, '[', ']');
		postfixValidation = removeParentheses(postfixValidation, '[', ']');
		
		// check if should add round parentheses for prefix's validation
		if (addParenthesesToPrefix) {
			prefixValidation = "(" + prefixValidation + ")";
		}
		
		// check if should add round parentheses for postfix's validation
		if (addParenthesesToPostfix) {
			postfixValidation = "(" + postfixValidation + ")";
		}
		
		// combine validation for both parts
		return "[" + prefixValidation + " and " + postfixValidation + "]";
	}
	
	/**
	 * Handles condition with "or", where "or"'s instance not between parentheses (free):
	 * verifies that at least one part can be validated, but shows validation for
	 * all sub expressions that could be validated
	 * @param condition- condition to be validated
	 * @param source- source node for the evaluation
	 * @param candidateIndex- index of candidate node among other candidates (counts from 1) 
	 * @return if exists- validation for the condition, otherwise- returns an empty string
	 */
	private String validateConditionWithOr(String condition, Node source, int candidateIndex) {

		// initialize string to hold condition validation
		String validation = "";
		
		// indicate if could validate each part of the condition
		boolean couldValidatePrefix = false;
		boolean couldValidatePostfix = false;
		
		// split condition by "or"
		List<String> conditionTokens = splitBooleanConditionByString(condition, "or");
		
		// check if prefix is between round parentheses
		boolean addParenthesesToPrefix = processTokenParentheses(conditionTokens, PREFIX_INDX);
				
		// validate prefix
		String prefixValidation = validateBooleanCondition(conditionTokens.get(PREFIX_INDX), source, candidateIndex);
		
		// check if the prefix is fulfilled
		if (!prefixValidation.equals("")) {
			
			// remove predicate parentheses from prefix
			prefixValidation = removeParentheses(prefixValidation, '[', ']');
			
			// check if should add round parentheses for prefix's validation
			if (addParenthesesToPrefix) {
				prefixValidation = "(" + prefixValidation + ")";
			}
			
			// add sub condition validation to entire condition validation
			validation = prefixValidation + " or ";
			
			// could validate prefix
			couldValidatePrefix = true;

		} else {
			
			// could not validate prefix
			if (addParenthesesToPrefix) { validation = "(" + conditionTokens.get(PREFIX_INDX) + ")" + " or "; }
			else { validation = conditionTokens.get(PREFIX_INDX) + " or "; }
		}
		
		// check if postfix is between round parentheses
		boolean addParenthesesToPostfix = processTokenParentheses(conditionTokens, POSTFIX_INDX);
		
		// validate postfix
		String postfixValidation = validateBooleanCondition(conditionTokens.get(POSTFIX_INDX), source, candidateIndex); 		
		
		// check if the postfix is fulfilled 
		if (!postfixValidation.equals("")) {
			
			// remove predicate parentheses from postfix
			postfixValidation = removeParentheses(postfixValidation, '[', ']');

			// check if should add round parentheses to prefix token
			if (addParenthesesToPrefix) {
				addRoundPrenthesesToToken(conditionTokens, PREFIX_INDX);
			}
			
			// check if should add round parentheses for postfix's validation
			if (addParenthesesToPostfix) {
				postfixValidation = "(" + postfixValidation + ")";
			}
			
			// add sub condition validation to entire condition validation
			validation = validation + postfixValidation;
			
			// could validate postfix
			couldValidatePostfix = true;

		} else {
			
			// could not validate postfix
			if (addParenthesesToPostfix) { validation = validation + "(" + conditionTokens.get(POSTFIX_INDX) + ")"; }
			else { validation = validation + conditionTokens.get(POSTFIX_INDX); }
		}
		
		// check if could validate condition
		if (couldValidatePrefix || couldValidatePostfix) { return "[" + validation + "]"; }
		
		// could not validate the condition
		return "";
	}
	
	/**
	 * Finds validation (proof) for given negative condition:
	 * Gets all candidate nodes that could fulfill the condition, using evaluate method.
	 * Gets all nodes that fulfill the condition using the xpath object.
	 * Finds first match between candidate and node that fulfills the condition.
	 * The validation is composed using the path claimed from the evaluate method and
	 * the index of the matching candidate node
	 * @param condition- boolean condition to be validated
	 * @param candidate- candidate node to be added (source node for test evaluations)
	 * @param candidateIndex- index of candidate node 
	 * @return if exists- validation for the boolean condition, otherwise- returns an empty string
	 */
	private String validateNegativeCondition(String condition, Node source, int candidateIndex) {

		// remove negation from condition
		String conditionRemovedNegation = removeNegationFromCondition(condition);
		
		// remove round parentheses
		condition = removeParentheses(condition, '(', ')');
		
		// check if condition is negative ( not(...) )
		if (isNegativeCondition(conditionRemovedNegation)) { 
 
			// try validating the condition without the negation
			String negativeValidation = validateNegativeCondition(conditionRemovedNegation, source, candidateIndex);
			 
			/*
			 * could not validate the condition wrapped with "not()", 
			 * then the validation is the condition itself 
			 */
			if (negativeValidation.equals("")) {
				return "[" + condition + "]";
			}
			
			/*
			 * condition wrapped with "not()" could be validated, 
			 * then the negative condition could not be validated 
			 */
			return "";
		}

		// check if condition is composed of "|"
		if (splitExpressions(conditionRemovedNegation, '|').size() > 1) { return validateNegativeConditionWithPipe(conditionRemovedNegation, source, candidateIndex); }
		
		// check if condition is composed of "and"
		if (!splitBooleanConditionByString(conditionRemovedNegation, "and").isEmpty()) { return validateNegativeConditionWithAnd(conditionRemovedNegation, source, candidateIndex); }
		
		// check if condition is composed of "or"
		if (!splitBooleanConditionByString(conditionRemovedNegation, "or").isEmpty()) { return validateNegativeConditionWithOr(conditionRemovedNegation, source, candidateIndex); }
		
		// split expression according to free instance of the operator
		List<String> conditionTokens = splitBooleanConditionByOperator(conditionRemovedNegation);

		// remove round parentheses from prefix
		boolean addParenToPrefix = false, addParenToPostfix = false;
		if (!conditionTokens.isEmpty()) {
			
			// check if should add back the round parentheses after the validation
			addParenToPrefix = processTokenParentheses(conditionTokens, PREFIX_INDX);
			addParenToPostfix = processTokenParentheses(conditionTokens, POSTFIX_INDX);
		}
		
		// sample the condition according to its tokens
		int expressionType = sampleBooleanCondition(conditionTokens);
		
		// lists to hold candidate nodes and nodes that fulfill the condition
		XpathNodeListImplementation candidateNodes = null;
		NodeList fulfillingNodes = null;
		
		String beforeOperator = null;
		
		// indicates if should place the path-proof at the postfix
		boolean isProofAtPostfix = false;
			
		try {
			
			// find condition validation according to sampling result 
			switch (expressionType) {
			case EXPRESSION_AT_PREFIX_ONLY: {
				
				// get the expression before the operator
				beforeOperator = conditionTokens.get(PREFIX_INDX);
	
				// compose expression to get nodes that fulfill the condition
				String fulfillingNodesExpression = composeFulfillingNodesExpression(
						conditionTokens.get(PREFIX_INDX),
						conditionTokens.get(OPERATOR_INDX),
						conditionTokens.get(POSTFIX_INDX), true, false);

				
				// get all nodes that fulfill the condition
				fulfillingNodes = (NodeList) xpath.evaluate(fulfillingNodesExpression, source, XPathConstants.NODESET);
				
				break;
			}
			
			case EXPRESSION_AT_POSTFIX_ONLY: {
				
				// get the expression before the operator
				beforeOperator = conditionTokens.get(POSTFIX_INDX);
	
				// compose expression to get nodes that fulfill the condition
				String fulfillingNodesExpression = composeFulfillingNodesExpression(
						conditionTokens.get(POSTFIX_INDX),
						conditionTokens.get(OPERATOR_INDX),
						conditionTokens.get(PREFIX_INDX), true, true);
				
				// get all nodes that fulfill the condition
				fulfillingNodes = (NodeList) xpath.evaluate(fulfillingNodesExpression, source, XPathConstants.NODESET);
				
				// swap prefix and postfix in condition's validation
				isProofAtPostfix = true;
				
				break;
			}
	
			case EXPRESSION_AT_BOTH_SIDES: {
				
				// validate the condition considering expressions at both sides of operator
				return handleConditionAtBothSides(conditionTokens, source, true, addParenToPrefix, addParenToPostfix);
			}
				
			case NO_EXPRESSION_AT_BOTH_SIDES: {
				
				// does not have to provide a validation to condition using a path
				return handleNoExpressionNearOperator(conditionTokens, source, true, candidateIndex);				
			}
			
			case SINGLE_TOKEN: {

				// check if should start evaluation from document root
				if (conditionRemovedNegation.charAt(0) == '/') { source = doc; }
				
				// check if condition is atomic
				if (conditionRemovedNegation.startsWith("true(") || conditionRemovedNegation.startsWith("false(")) {
					
					// try validating
					String validation = handleAtomicCondition(conditionRemovedNegation, source);
					
					// check if can validated condition in a negative manner
					if (validation.equals("")) {
						
						// could not validated condition without negation- therefore condition is fulfilled
						return "[" + condition + "]";
					}
					
					// could not validate condition
					return "";
				}
				
				// validate condition without negation
				String validation = validateConditionNoBooleanOperator(conditionRemovedNegation, source);
				if (validation.equals("")) {
					
					// could not validated condition without negation- therefore condition is fulfilled
					return "[" + condition + "]";
				}
				
				// could not validate condition
				return "";
			}
				
			case ID_AT_PREFIX: {

				// split prefix to segments
				List<String> prefixSegments = splitExpressions(conditionTokens.get(PREFIX_INDX), '/');
				
				// compose expression to get relevant nodes
				String fulfillingNodesExpression = prefixSegments.get(0) + "[not(" 
												   + conditionTokens.get(PREFIX_INDX).substring(prefixSegments.get(0).length()+1) 
												   + conditionTokens.get(OPERATOR_INDX) 
												   + conditionTokens.get(POSTFIX_INDX) + ")]";
				
				// get fulfilling nodes
				fulfillingNodes = (NodeList) xpath.evaluate(fulfillingNodesExpression, source, XPathConstants.NODESET);
				
				// get candidate nodes
				String candidatesExpression = prefixSegments.get(0);
				XpathNodeListImplementation candidates = (XpathNodeListImplementation) evaluate(candidatesExpression, source, XPathConstants.NODESET);
				
				// get nodes resulting from expression at prefix
				XpathNodeListImplementation prefixNodes = (XpathNodeListImplementation) evaluate(conditionTokens.get(PREFIX_INDX), source, XPathConstants.NODESET);
				
				// return validation for the entire condition
				return handleIDAtOneSide(conditionTokens, prefixNodes.getPathList(), candidates, fulfillingNodes, false, true, addParenToPrefix, addParenToPostfix);	
			}
			
			case ID_AT_POSTFIX: {
			
				// split postfix to segments
				List<String> postfixSegments = splitExpressions(conditionTokens.get(POSTFIX_INDX), '/');
				
				// compose expression to get relevant nodes
				String fulfillingNodesExpression = postfixSegments.get(0) + "[not(" 
												   + conditionTokens.get(PREFIX_INDX) 
												   + conditionTokens.get(OPERATOR_INDX) 
												   + conditionTokens.get(POSTFIX_INDX).substring(postfixSegments.get(0).length()+1) + ")]";
				
				// get fulfilling nodes
				fulfillingNodes = (NodeList) xpath.evaluate(fulfillingNodesExpression, source, XPathConstants.NODESET);
				
				// get candidate nodes
				String candidatesExpression = postfixSegments.get(0);
				XpathNodeListImplementation candidates = (XpathNodeListImplementation) evaluate(candidatesExpression, source, XPathConstants.NODESET);
				
				// get nodes resulting from expression at postfix
				XpathNodeListImplementation postfixNodes = (XpathNodeListImplementation) evaluate(conditionTokens.get(POSTFIX_INDX), source, XPathConstants.NODESET);
				
				// return validation for the entire condition
				return handleIDAtOneSide(conditionTokens, postfixNodes.getPathList(), candidates, fulfillingNodes, true, true, addParenToPrefix, addParenToPostfix);
			}	
			
			default:
				break;
			}

			// get candidates for condition with expression at only one side of the operator			
			candidateNodes = getCandidateNodes(beforeOperator, source);

			// check if there are no candidates
			if (candidateNodes.getLength() == 0) {
				
				// no candidates for the condition- negative condition is validated
				return "[" + condition + "]";
			}

			// handle a negative expression at only one side of the operator
			return handleExpressionAtOneSide(conditionTokens, beforeOperator,
					candidateNodes, fulfillingNodes, isProofAtPostfix, true,
					addParenToPrefix, addParenToPostfix);
	
		} catch (XPathExpressionException e1) {

			// no validation
			return "";
			
		} catch (IllegalArgumentException e1) {

			// no validation
			return "";
			
		} catch (NullPointerException e1) {

			// no validation
			return "";
		}
	}
	
	/**
	 * Splits given condition by free instances of "|" and evaluates each sub condition separately.
	 * Since this condition is fulfilled if expression results in a non-empty node set,
	 * condition is validated if each sub condition could not be validated.
	 * Validation is returned as original condition
	 * @param condition- condition to be evaluated
	 * @param source- source node for the evaluation
	 * @return if exists- validation for the condition, otherwise- returns an empty string
	 */
	private String validateNegativeConditionWithPipe(String condition, Node source, int candidateIndex) {
		
		// split condition by free instances of "|"
		List<String> subConditions = splitExpressions(condition, '|');
		
		// check if any sub condition can be validated
		int numOfSubConditions = subConditions.size();
		for (int i = 0 ; i < numOfSubConditions ; ++i) {
			
			// get validation of current sub condition
			String currSubCondValidation = validateBooleanCondition(subConditions.get(i), source, candidateIndex);
			
			// check if could validate
			if (!currSubCondValidation.equals("")) {

				// could validate current sub condition
				return "";
			}
		}
		
		// return validation for the negative condition
		return "[not(" + condition + ")]";
	}
	
	/**
	 * Handles a negative condition with "and", where "and"'s instance not between parentheses (free):
	 * verifies that at least one part cannot be validated
	 * @param condition- condition to be validated
	 * @param source- source node for the evaluation
	 * @param candidateIndex- index of candidate node among other candidates (counts from 1)
	 * @return if exists- validation for the condition being not fulfilled, otherwise- returns an empty string
	 */
	private String validateNegativeConditionWithAnd(String condition, Node source, int candidateIndex) {

		// split condition by "and"
		List<String> conditionTokens = splitBooleanConditionByString(condition, "and");
		
		// check if prefix is between round parentheses
		boolean addParenthesesToPrefix = processTokenParentheses(conditionTokens, PREFIX_INDX);
				
		// validate prefix as a negative condition
		String prefixValidation = validateNegativeCondition(conditionTokens.get(PREFIX_INDX), source, candidateIndex);
		
		// check if could validate prefix as a negative condition
		if (!prefixValidation.equals("")) {
			
			// remove predicate parentheses from prefix
			prefixValidation = removeParentheses(prefixValidation, '[', ']');
			
			// remove negation from prefix
			prefixValidation = removeNegationFromCondition(prefixValidation);
			
			// check if should add round parentheses for prefix's validation
			if (addParenthesesToPrefix) {
				prefixValidation = "(" + prefixValidation + ")";
			}
			
			// return validation for the entire condition
			return "[not(" + prefixValidation + " and " + conditionTokens.get(POSTFIX_INDX) + ")]";
		}
		
		// check if postfix is between round parentheses
		boolean addParenthesesToPostfix = processTokenParentheses(conditionTokens, POSTFIX_INDX);
		
		// validate postfix as a negative condition 		
		String postfixValidation = validateNegativeCondition(conditionTokens.get(POSTFIX_INDX), source, candidateIndex);
		
		// check if could validate postfix as a negative condition 
		if (!postfixValidation.equals("")) {
			
			// remove predicate parentheses from postfix
			postfixValidation = removeParentheses(postfixValidation, '[', ']');

			// remove negation from postfix
			postfixValidation = removeNegationFromCondition(postfixValidation);
			
			// check if should add round parentheses to prefix token
			if (addParenthesesToPrefix) {
				addRoundPrenthesesToToken(conditionTokens, PREFIX_INDX);
			}
			
			// check if should add round parentheses for postfix's validation
			if (addParenthesesToPostfix) {
				postfixValidation = "(" + postfixValidation + ")";
			}
			
			// return validation for the entire condition
			return "[not(" + conditionTokens.get(PREFIX_INDX) + " or " + postfixValidation + ")]";
		}
		
		// could not validate the condition
		return "";
	}

	/**
	 * Handles a negative condition with "or", where "or"'s instance not between parentheses (free):
	 * verifies that at both parts cannot be validated
	 * @param condition- condition to be validated
	 * @param source- source node for the evaluation
	 * @param candidateIndex- index of candidate node among other candidates (counts from 1)
	 * @return if exists- validation for the condition being not fulfilled, otherwise- returns an empty string
	 */
	private String validateNegativeConditionWithOr(String condition, Node source, int candidateIndex) {

		// split condition by "or"
		List<String> conditionTokens = splitBooleanConditionByString(condition, "or");

		// check if prefix is between round parentheses
		boolean addParenthesesToPrefix = processTokenParentheses(conditionTokens, PREFIX_INDX);
		
		// validate prefix as a negative condition
		String prefixValidation = validateNegativeCondition(conditionTokens.get(PREFIX_INDX), source, candidateIndex);
		
		// check if postfix is between round parentheses
		boolean addParenthesesToPostfix = processTokenParentheses(conditionTokens, POSTFIX_INDX);
		
		// validate postfix as a negative condition
		String postfixValidation = validateNegativeCondition(conditionTokens.get(POSTFIX_INDX), source, candidateIndex);
		
		// check could not validate both parts as negative condition
		if (prefixValidation.equals("") || postfixValidation.equals("")) {
			
			// at least one part is fulfilled
			return "";
		}
		
		// remove predicate parentheses from both parts
		prefixValidation = removeParentheses(prefixValidation, '[', ']');
		postfixValidation = removeParentheses(postfixValidation, '[', ']');
		
		// remove negation from both parts
		prefixValidation = removeNegationFromCondition(prefixValidation);
		postfixValidation = removeNegationFromCondition(postfixValidation);
		
		// check if should add round parentheses for prefix's validation
		if (addParenthesesToPrefix) {
			prefixValidation = "(" + prefixValidation + ")";
		}
		
		// check if should add round parentheses for postfix's validation
		if (addParenthesesToPostfix) {
			postfixValidation = "(" + postfixValidation + ")";
		}
		
		// combine validation for both parts
		return "[not(" + prefixValidation + " or " + postfixValidation + ")]";
	}
	
	/**
	 * Samples the boolean condition according to its tokens. Checks if condition is
	 * one of the following:
	 * 1.expression only before operator
	 * 2. expression only after operator
	 * 3. two expressions at both sides of the operator
	 * 4. no expression at both sides of the operator
	 * 5. a single token (no operator)
	 * 6. expression with id only before operator, and no expression after operator
	 * 7. expression with id only after operator, and no expression before operator
	 * After sampling is done, returns a numeric value that represents the sampling result. 
	 * @param conditionTokens- tokens of boolean condition to be sampled
	 * @return numeric value representing the sampling result, or NUMERIC_ERROR_VAL in case of error
	 */	
	private int sampleBooleanCondition(List<String> conditionTokens) {
		
		// initialize flags used to determine the sampling result
		boolean isExpressionAtPrefix = true;
		boolean isExpressionAtPostfix = true;
		boolean isIDAtPrefix = false;
		boolean isIDAtPostfix = false;
		
		// check if condition is composed of a single token
		if (conditionTokens.size() == 0) { return SINGLE_TOKEN; }

		// get segments of prefix and postfix tokens
		List<String> prefixSegments = splitExpressions(conditionTokens.get(PREFIX_INDX), '/');
		List<String> postfixSegments = splitExpressions(conditionTokens.get(POSTFIX_INDX), '/');
		String prefixFirstSegment = prefixSegments.get(0);
		String postfixFirstSegment = postfixSegments.get(0);

		// remove conditions from first segment of each token
		prefixFirstSegment = getExpressionWithoutCondition(prefixFirstSegment);
		postfixFirstSegment = getExpressionWithoutCondition(postfixFirstSegment);
		
		// remove round parentheses from the first segment of each token
		prefixFirstSegment = removeParentheses(prefixFirstSegment, '(', ')');
		postfixFirstSegment = removeParentheses(postfixFirstSegment, '(', ')');

		// check if both prefix and postfix use id()
		if (prefixFirstSegment.startsWith("id(")
				&& postfixFirstSegment.startsWith("id(")) {
			return EXPRESSION_AT_BOTH_SIDES;
		}
		
		// check if prefix token is an expression
		try {

			xpath.compile("self::node()/" + conditionTokens.get(PREFIX_INDX)
					+ "[text()" + conditionTokens.get(OPERATOR_INDX)
					+ conditionTokens.get(POSTFIX_INDX) + "]");

		} catch (XPathExpressionException e) {

			// check if prefix uses id()
			if (prefixFirstSegment.startsWith("id(")) {
				isIDAtPrefix = true;
			}
			
			// prefix is not an expression
			isExpressionAtPrefix = false;
		}
		
		// check if postfix token is an expression
		try {			

			xpath.compile("self::node()/" + conditionTokens.get(POSTFIX_INDX)
					+ "[text()" + conditionTokens.get(OPERATOR_INDX)
					+ conditionTokens.get(PREFIX_INDX) + "]");
			
		} catch (XPathExpressionException e) {

			// check if postfix uses id()
			if (postfixFirstSegment.startsWith("id(")) {
				isIDAtPostfix = true;
			}
			
			// postfix is not an expression
			isExpressionAtPostfix = false;
		}
		
		// return result according to flags' value
		
		/*
		 * check all options for expressions at both sides:
		 * 1. found expression at prefix and postifx
		 * 2. found expressions with id() at both sides
		 * 3. found expression at prefix and expression with id() at postfix
		 * 4. found expression with id() at prefix and expression at postfix
		 */
		if ((isExpressionAtPrefix && isExpressionAtPostfix) 
				|| (isIDAtPrefix && isIDAtPostfix)
				|| (isExpressionAtPrefix && isIDAtPostfix)
				|| (isExpressionAtPostfix && isIDAtPrefix)) {
			
			// both prefix and postfix hold an expression
			return EXPRESSION_AT_BOTH_SIDES;
		}
		
		// check if expression is at prefix only and it involves id()
		if (isIDAtPrefix && !isExpressionAtPostfix) {
			return ID_AT_PREFIX;
		}
		
		// check if expression is at postfix only and it involves id()
		if (isIDAtPostfix && !isExpressionAtPrefix) {
			return ID_AT_POSTFIX;
		}
		
		// check if expression is at prefix only
		if (isExpressionAtPrefix && !isIDAtPostfix) {
			return EXPRESSION_AT_PREFIX_ONLY;
		}
		
		// check if expression is at postfix only
		if (isExpressionAtPostfix && !isExpressionAtPrefix) {
			return EXPRESSION_AT_POSTFIX_ONLY;
		}
		
		// both operator's sides do not hold an expression		
		return NO_EXPRESSION_AT_BOTH_SIDES;
	}
	
	/**
	 * Gets the candidate nodes that could fulfill the condition (that is composed of two operands).
	 * If the condition's operand is text() or an attribute, the candidate is the source node.
	 * Otherwise, the method evaluates the expression that is before the operator and returns the nodes 
	 * and validations found
	 * @param beforeOperator- condition part that is before the operator
	 * @param source- source node for the evaluation
	 * @return candidate nodes and their validations
	 * @throws XPathExpressionException if had problems evaluating the expression
	 * @throws IllegalArgumentException if had problems evaluating the expression
	 * @throws NullPointerException if had problems evaluating the expression
	 */
	private XpathNodeListImplementation getCandidateNodes(String beforeOperator, Node source)
			throws XPathExpressionException, IllegalArgumentException,
			NullPointerException {

		// check if should evaluate from document's root element
		if (beforeOperator.charAt(0) == '/') {
			source = doc;
		}
		
		// replace axis abbreviations
		if (beforeOperator.equals(".")) { beforeOperator = "self::node()"; }
		if (beforeOperator.equals("..")) { beforeOperator = "parent::node()"; }
		
		// initialize list to hold candidate nodes
		XpathNodeListImplementation candidateNodes = new XpathNodeListImplementation();
		
		// split the part before the operator to segments
		List<String> segments = splitExpressions(beforeOperator, '/');
		
		// check if have multiple segments
		if (segments.size() > 1) {
			
			// check the last segment does not result in a node
			String lastSegment = segments.get(segments.size()-1);		 
			if (notNodeCandidate(lastSegment)) {
				
				// remove last segment from the part before the operator
				String expression = segments.get(0);
				int segmentsToConcatenate = segments.size()-1;
				for (int i = 1 ; i < segmentsToConcatenate ; ++i) {
					
					// build new expression
					expression = expression + "/" + segments.get(i);
				}
				
				// find previous node candidate
				candidateNodes = getCandidateNodes(expression, source);
				
				// add back last segment to each candidate's path
				List<String> fullPaths = concatenatePaths(candidateNodes.getPathList(), "/" + segments.get(segments.size()-1));
				
				// update candidates' paths
				int numOfCandidates = candidateNodes.getLength();
				for (int i = 0 ; i < numOfCandidates ; ++i) {
					candidateNodes.setItemPath(fullPaths.get(i), i);
				}
				
			} else {
		
				// get candidates according to the expression before the operator
				candidateNodes = (XpathNodeListImplementation) evaluate(beforeOperator, source, XPathConstants.NODESET);
			}			
 
		} else if (notNodeCandidate(beforeOperator)) { // check if part before operator does not result in a node
		
			// source node is the candidate
			candidateNodes.addNode(new AbstractMap.SimpleEntry<Node, String>(source, "/"+beforeOperator));
			
		} else { // candidate is a node
	
			// get candidates according to the expression before the operator
			candidateNodes = (XpathNodeListImplementation) evaluate(beforeOperator, source, XPathConstants.NODESET);
		}
		
		// return candidate nodes found
		return candidateNodes;		
	}
	
	/**
	 * Validates boolean condition where one side of the operator is an xpath expression and
	 * the other side is not.
	 * Finds first candidate that matches a first node that fulfills the condition,
	 * and composes the validation string.
	 * If condition is negative, validation is wrapped with "not()".
	 * Adds round parentheses to prefix and postfix if necessary
	 * @param conditionTokens- condition after being split by the operator
	 * @param beforeOperator- the part before the operator
	 * @param candidateNodes- nodes that could fulfill the condition
	 * @param fulfillingNodes- nodes that fulfill the condition
	 * @param isProofAtPostfix- indicates if the validation should appear at the postfix
	 * @param isNegative- indicates if condition is negative
	 * @param addParenToPrefix- indicates if should add round parentheses to prefix
	 * @param addParenToPostfix- indicates if should add round parentheses to postfix
	 * @return if exists- validation for the condition, otherwise- returns an empty string
	 */
	private String handleExpressionAtOneSide(List<String> conditionTokens,
			String beforeOperator, XpathNodeListImplementation candidateNodes,
			NodeList fulfillingNodes, boolean isProofAtPostfix,
			boolean isNegative, boolean addParenToPrefix,
			boolean addParenToPostfix) {
		
		// check if condition is fulfilled
		if (fulfillingNodes.getLength() == 0) {
			
			// no proof for the condition
			return "";
		}
		
		// first node on this list proves the condition
		Node provingNode = fulfillingNodes.item(0);
		
		// find first candidate that fulfills the condition
		int numOfCandidates = candidateNodes.getLength();
		for (int i = 0 ; i < numOfCandidates ; ++i) {
			
			// compare current candidate to proving node
			if (candidateNodes.item(i).isSameNode(provingNode)) {
				
				// initialize "wrappers" for negative condition
				String negativeStart = "";
				String negativeEnd = "";
				
				// check if condition is negative
				if (isNegative) {
				
					// condition should be wrapped
					negativeStart = "not(";
					negativeEnd = ")";
				}
				
				// check if should add round parentheses
				String prefixParenStart = "", prefixParenEnd = "", postfixParenStart = "", postfixParenEnd = "";
				if (addParenToPrefix) { prefixParenStart = "(";	prefixParenEnd = ")"; }
				if (addParenToPostfix) { postfixParenStart = "("; postfixParenEnd = ")"; }
				
				// return proof for the condition
				if (isProofAtPostfix) {
					
					// place proof at the postfix
					return "["
							+ negativeStart
							+ prefixParenStart
							+ conditionTokens.get(PREFIX_INDX)
							+ prefixParenEnd
							+ conditionTokens.get(OPERATOR_INDX)
							+ postfixParenStart
							+ candidateNodes.itemPath(i).substring(1,
									candidateNodes.itemPath(i).length())
							+ postfixParenEnd
							+ negativeEnd + "]";
				}
				
				// place proof at the prefix
				return "["
						+ negativeStart
						+ prefixParenStart
						+ candidateNodes.itemPath(i).substring(1,
								candidateNodes.itemPath(i).length())
						+ prefixParenEnd
						+ conditionTokens.get(OPERATOR_INDX)
						+ postfixParenStart
						+ conditionTokens.get(POSTFIX_INDX)
						+ postfixParenEnd
						+ negativeEnd + "]";
			}
		}
		
		// did not find- return ""
		return "";
	}
	
	/**
	 * Validates boolean condition where one side of the operator is an xpath expression
	 * involving id() function, and the other side is not an expression.
	 * Finds first candidate that matches a first node that fulfills the condition,
	 * and composes the validation string.
	 * If condition is negative, validation is wrapped with "not()".
	 * Adds round parentheses to prefix and postfix if necessary
	 * @param conditionTokens- condition after being split by the operator
	 * @param candidatesValidations
	 * @param candidateNodes- nodes that could fulfill the condition
	 * @param fulfillingNodes- nodes that fulfill the condition
	 * @param isProofAtPostfix- indicates if the validation should appear at the postfix
	 * @param isNegative- indicates if condition is negative
	 * @param addParenToPrefix- indicates if should add round parentheses to prefix
	 * @param addParenToPostfix- indicates if should add round parentheses to postfix
	 * @return if exists- validation for the condition, otherwise- returns an empty string
	 */
	private String handleIDAtOneSide(List<String> conditionTokens,
			List<String> candidatesValidations, XpathNodeListImplementation candidateNodes,
			NodeList fulfillingNodes, boolean isProofAtPostfix,
			boolean isNegative, boolean addParenToPrefix,
			boolean addParenToPostfix) {
		
		// check if condition is fulfilled
		if (fulfillingNodes.getLength() == 0) {
			
			// no proof for the condition
			return "";
		}
		
		// first node on this list proves the condition
		Node provingNode = fulfillingNodes.item(0);
		
		// check if should add round parentheses
		String prefixParenStart = "", prefixParenEnd = "", postfixParenStart = "", postfixParenEnd = "";
		if (addParenToPrefix) { prefixParenStart = "(";	prefixParenEnd = ")"; }
		if (addParenToPostfix) { postfixParenStart = "("; postfixParenEnd = ")"; }
		
		// find first candidate that fulfills the condition
		int numOfCandidates = candidateNodes.getLength();
		for (int i = 0 ; i < numOfCandidates ; ++i) {
			
			// compare current candidate to proving node
			if (candidateNodes.item(i).isSameNode(provingNode)) {
				
				// initialize "wrappers" for negative condition
				String negativeStart = "";
				String negativeEnd = "";
				
				// check if condition is negative
				if (isNegative) {
				
					// condition should be wrapped
					negativeStart = "not(";
					negativeEnd = ")";
				}
				
				// return proof for the condition
				if (isProofAtPostfix) {
					
					// place proof at the postfix
					return "["
							+ negativeStart
							+ prefixParenStart
							+ conditionTokens.get(PREFIX_INDX)
							+ prefixParenEnd
							+ conditionTokens.get(OPERATOR_INDX)
							+ postfixParenStart
							+ candidatesValidations.get(i).substring(1)
							+ postfixParenEnd
							+ negativeEnd + "]";
				}
				
				// place proof at the prefix
				return "["
						+ negativeStart
						+ prefixParenStart
						+ candidatesValidations.get(i).substring(1)
						+ prefixParenEnd
						+ conditionTokens.get(OPERATOR_INDX)
						+ postfixParenStart
						+ conditionTokens.get(POSTFIX_INDX)
						+ postfixParenEnd
						+ negativeEnd + "]";
			}
		}
		
		// did not find- return ""
		return "";
	}
	
	/**
	 * Gets nodes that fulfill each side of the condition (prefix and postfix).
	 * Compares two nodes lists and returns validation for first nodes that fulfill
	 * the condition.
	 * If condition is negative, performs the comparison in a negative manner
	 * @param conditionTokens- tokens of condition to be validated
	 * @param source- source node
	 * @param isNegative- indicates if condition is negative
	 * @param addParenToPrefix- indicates if should add round parentheses to prefix
	 * @param addParenToPostfix- indicates if should add round parentheses to postfix
	 * @return if exists- validation to condition, otherwise- empty string
	 * @throws XPathExpressionException thrown if xpath evaluation has encountered a problem
	 */
	private String handleConditionAtBothSides(List<String> conditionTokens,
			Node source, boolean isNegative, boolean addParenToPrefix,
			boolean addParenToPostfix) throws XPathExpressionException {
		
		// source nodes for each part's evaluation
		Node prefixSource = source;
		Node postfixSource = source;

		// check if should evaluate prefix from document's root element
		if (conditionTokens.get(PREFIX_INDX).charAt(0) == '/') {
			prefixSource = doc;
		}
		
		// get nodes that fulfill the prefix
		XpathNodeListImplementation prefixNodes = (XpathNodeListImplementation) evaluate(conditionTokens.get(PREFIX_INDX), prefixSource, XPathConstants.NODESET);

		// check if should evaluate postfix from document's root element
		if (conditionTokens.get(POSTFIX_INDX).charAt(0) == '/') {
			postfixSource = doc;
		}		
		
		// get nodes that fulfill the postfix
		XpathNodeListImplementation postfixNodes = (XpathNodeListImplementation) evaluate(conditionTokens.get(POSTFIX_INDX), postfixSource, XPathConstants.NODESET);

		// check if should add round parentheses
		String prefixParenStart = "", prefixParenEnd = "", postfixParenStart = "", postfixParenEnd = "";
		if (addParenToPrefix) { prefixParenStart = "(";	prefixParenEnd = ")"; }
		if (addParenToPostfix) { postfixParenStart = "("; postfixParenEnd = ")"; }
		
		// check if both parts are fulfilled
		if (0 == prefixNodes.getLength() || 0 == postfixNodes.getLength()) {

			// if condition is negative, it has been validated
			if (isNegative) {
				
				// return validation
				return "[not(" + prefixParenStart + conditionTokens.get(PREFIX_INDX) + prefixParenEnd 
						+ conditionTokens.get(OPERATOR_INDX) 
						+ postfixParenStart + conditionTokens.get(POSTFIX_INDX) + postfixParenEnd + ")]";
			}
			
			// at least one part is not fulfilled
			return "";
		}

		// check if comparison should be negative
		String negativeStart = "";
		String negativeEnd = "";
		if (isNegative) {
			negativeStart = "not(";
			negativeEnd = ")";
		}		
		
		// find first nodes that match the comparison
		int numOfPrefixNodes = prefixNodes.getLength();
		int numOfPostfixNodes = postfixNodes.getLength();
		for (int i = 0; i < numOfPrefixNodes; ++i) {			
			for (int j = 0; j < numOfPostfixNodes; ++j) {
				
				/*
				 * compose the xpath expression needed for comparing current nodes.
				 * add round parentheses to keep original context when applying index ("[i+1]", "[j+1]")
				 */
				String comparisonExpression = negativeStart 
												+ "(" + conditionTokens.get(PREFIX_INDX) + ")[" + (i + 1)	+ "]" 
												+ conditionTokens.get(OPERATOR_INDX) 
												+ "(" + conditionTokens.get(POSTFIX_INDX) + ")[" + (j + 1) + "]" 
												+ negativeEnd;
				
				// check if current nodes fulfill the condition
				boolean nodesAreEqual = (boolean) xpath.evaluate(comparisonExpression, source, XPathConstants.BOOLEAN);
				if (nodesAreEqual) {

					// compose validation according to path node of each part
					return "[" + negativeStart 
							+ prefixParenStart + prefixNodes.itemPath(i).substring(1) + prefixParenEnd 
							+ conditionTokens.get(OPERATOR_INDX) 
							+ postfixParenStart + postfixNodes.itemPath(j).substring(1) + postfixParenEnd 
							+ negativeEnd + "]";
				}
			}
		}

		// could not validate condition
		return "";
	}
	
	/** 
	 * In this case, the condition is not related to child elements or attributes
	 * of the source node, hence the candidates are the siblings of the source node.
	 * Therefore, method gets all the siblings of source node and returns first
	 * node that fulfills the condition.
	 * Any instance of position() function in context of candidate node, is replaced
	 * with given candidate index 
	 * @param conditionTokens- tokens of condition to be validated
	 * @param source- source node
	 * @param isNegative- indicates if condition is negative
	 * @param candidateIndex- index of candidate node among other candidates (counts from 1)
	 * @return if exists- validation to condition, otherwise- empty string
	 * @throws XPathExpressionException thrown if xpath evaluation has encountered a problem
	 */
	private String handleNoExpressionNearOperator(List<String> conditionTokens,
			Node source, boolean isNegative, int candidateIndex)
			throws XPathExpressionException {
	
		// check if comparison should be negative
		String negativeStart = "";
		String negativeEnd = "";
		if (isNegative) {
			negativeStart = "not(";
			negativeEnd = ")";
		}

		// compose condition string		
		String condition = negativeStart + 
				conditionTokens.get(PREFIX_INDX) + conditionTokens.get(OPERATOR_INDX) + conditionTokens.get(POSTFIX_INDX) 
				+ negativeEnd;
		
		// replace calls to "position()" referring current candidate node 
		String conditionWithPositionValue = replacePositionWithValue(condition, candidateIndex);
		
		// get nodes that fulfill the condition
		NodeList results = (NodeList) xpath.evaluate("self::node()" + "["+conditionWithPositionValue+"]", source, XPathConstants.NODESET);
		
		// check if source node fulfills the condition
		int numOfResults = results.getLength();
		for (int i = 0 ; i < numOfResults ; ++ i) {
		
			// check if current result is equal to source node
			if (results.item(i).isSameNode(source)) {
				
				// return validation
				return "[" + condition + "]";
			}
		}
				
		// could not validate condition
		return "";
	}
	
	/**
	 * Checks if given source node fulfills given condition, when no processing is necessary.
	 * If so, returns the condition as the validation. Otherwise, returns an empty string
	 * @param condition- condition to be validated
	 * @param source- source node
	 * @return if exists- validation to condition, otherwise- empty string
	 * @throws XPathExpressionException
	 */
	private String handleAtomicCondition(String condition, Node source) throws XPathExpressionException {
		
		// get nodes that fulfill the condition
		NodeList results = (NodeList) xpath.evaluate("self::node()" + "["+condition+"]", source, XPathConstants.NODESET);
		
		// check if source node fulfills the condition
		int numOfResults = results.getLength();
		for (int i = 0 ; i < numOfResults ; ++ i) {
		
			// check if current result is equal to source node
			if (results.item(i).isSameNode(source)) {
				
				// return validation
				return "[" + condition + "]";
			}
		}
		
		// could not validate condition
		return "";
	}
	
	// Methods used for processing on expressions (and conditions) strings
	
	/**
	 * Detects the delimiter arithmetic operator and splits the given xpath expression
	 * according to this operator.
	 * An expression of the form X + Y is converted to X + -Y in order to compute result
	 * correctly when splitting for sub expressions
	 * An operator is a delimiter if there is a free instance of it.
	 * @param expression- expression to be split
	 * @return tokens after the split
	 */
	private List<String> splitByArithmeticOperator(String expression) {
		
		// initialize list to hold the tokens
		List<String> tokens = new LinkedList<String>();
				
		// try splitting according to each operator, start with operators of lower precedence
	
		// try splitting by "+" 
		tokens = splitBooleanConditionByString(expression, "+");
		if (!tokens.isEmpty()) { return tokens; }
		
		// try splitting by "-" 
		tokens = splitBooleanConditionByString(expression, "-");
		if (!tokens.isEmpty()) {
			
			// replace the operator "-" with "+-"
			tokens.remove(OPERATOR_INDX);
			tokens.add(OPERATOR_INDX, "+");
			String postfix = tokens.remove(POSTFIX_INDX);
			tokens.add(POSTFIX_INDX, "-" + postfix);
			return tokens; 
		}
		
		// try splitting by "*" 
		tokens = splitBooleanConditionByString(expression, "*");
		if (!tokens.isEmpty()) { return tokens; }
		
		// try splitting by "div" 
		tokens = splitBooleanConditionByString(expression, "div");
		if (!tokens.isEmpty()) { return tokens; }
		
		// try splitting by "mod" 
		tokens = splitBooleanConditionByString(expression, "mod");
		if (!tokens.isEmpty()) { return tokens; }
		
		// could not split
		return tokens;
	}
	
	/**
	 * Gets a source string and returns the index of given substring's
	 * first free instance in source string.
	 * A free instance is an instance that is not between parentheses 
	 * @param source- string where should search substring
	 * @param substring- substring to check in source
	 * @return index of substring's first free instance in source string.
	 *         If substring does not have any free instance in source,
	 *         returns NUMERIC_ERROR_VAL
	 */
	public int indexOfFirstFreeInstance(String source, String substring) {

		int index = 0; // holds index of substring's first free instance
		int step = substring.length(); // how many chars should step after finding an instance
		String partToCheck = source; // source's part to be checked
		int skippedChars = 0; // number of chars skipped in source string when finding next instance
		
		// search first free instance of substring in source string
		while(partToCheck.indexOf(substring) != -1) {
			
			// get first instance of substring
			index = partToCheck.indexOf(substring);
			
			// check if instance found is free
			String prefix = partToCheck.substring(0, index);
			if (isParenthesesValid(prefix)) {
				
				// found first free instance
				return index + skippedChars;
			}
		
			// instance found is not free, check if reached source string's end
			if ((index + step) >= partToCheck.length()) { break; }
			
			// find where parentheses are balanced after instance found
			for (int i = index+step ; i <= partToCheck.length() ; ++i) {
				
				// find prefix until parentheses are balanced
				String balancedPrefix = partToCheck.substring(0, i); 
				if (isParenthesesValid(balancedPrefix)) { 
					
					// increment number of characters that are skipped in source string
					skippedChars += balancedPrefix.length();
					
					// remove prefix that keeps parentheses balanced
					partToCheck = partToCheck.substring(i);
					break; 
				}
			}
		}
		
		// could not find a free instance
		return NUMERIC_ERROR_VAL;
	}
	
	/**
	 * Checks if return type is valid, which means one of the types defined in XPathConstants:
	 * NUMBER, STRING, BOOLEAN, NODE, NODESET.
	 * @param returnType- return type to check
	 * @return True if return type is valid, False if not
	 */
	private boolean isReturnTypeValid(QName returnType) {

		// check if given return type is one of the xpath constants
		if (XPathConstants.NUMBER.equals(returnType)
				|| XPathConstants.STRING.equals(returnType)
				|| XPathConstants.BOOLEAN.equals(returnType)
				|| XPathConstants.NODE.equals(returnType)
				|| XPathConstants.NODESET.equals(returnType)) {
			return true;
		}
		
		// return type is not valid
		return false;
	}

	/**
	 * Removes condition from given expression, and checks if 
	 * remaining part has a reverse axis
	 * @param expression- expression to be checked
	 * @return True if has a reverse axis, False if not
	 */
	private boolean hasReverseAxes(String expression) {

		return (getExpressionWithoutCondition(expression).contains("ancestor") 
				|| getExpressionWithoutCondition(expression).contains("preceding"));
	}
	
	/**
	 * Gets the xpath expression to be evaluated and replaces an abbreviation for
	 * an axis with the axis itself:
	 * "//" is replaced with "/descendant-or-self::node()/"
	 * "../" is replaced with "parent::node()/"
	 * "/.." is replaced with "/parent::node()"
	 * "./" is replaced with "self::node()/"
	 * "/." is replaced with "/self::node()"
	 * @param expression- xpath expression to be processed
	 * @return expression after replacing the axis abbreviations
	 */
	private String replaceAbbrvWithAxis(String expression) {
		
		// replace abbreviations of "//"
		expression = expression.replace("//", "/descendant-or-self::node()/");
		
		// replace abbreviations of ".."
		expression = expression.replace("../", "parent::node()/");		
		expression = expression.replace("/..", "/parent::node()");
		
		// replace abbreviations of "."
		expression = expression.replace("./", "self::node()/");		
		expression = expression.replace("/.", "/self::node()");		
		
		// return the processed expression
		return expression;
	}

	/**
	 * Splits an expression to sub-expressions between free instances of the delimiter character.
	 * A free instance is one not between parentheses.
	 * The spaces of each sub expression found are trimmed
	 * @param expression- expression to split
	 * @param delimiter- character dividing free sub expressions
	 * @return expressions between free instances of the delimiter
	 */
	private List<String> splitExpressions(String expression, char delimiter) {

		// list to hold the sub expressions
		List<String> subExprs = new LinkedList<String>();
		
		// scan the expression from left to write and find first free delimiter
		int length = expression.length();
		char[] chars = expression.toCharArray();
		int openFuncParenCtr = 0; // counts successive opening parentheses of a function- "(" 
		int openPredicateParenCtr = 0; // counts successive opening parentheses of a predicate- "["
		int closePredicateParenCtr = 0; // counts successive closing parentheses of a predicate- "]"
		int closeFuncParenCtr = 0; // counts successive closing parentheses of a function- ")"
		int currSubExprStart = 0; // start index of current extracted sub expression
		
		for (int i = 0 ; i < length ; ++ i) {
						
			// check if opened function parentheses
			if ( '(' == chars[i]) {
				
				// update counter
				++openFuncParenCtr;
				
				// read next character
				continue;
			}
			
			// check if closed function parentheses
			if ( ')' == chars[i]) {
				
				// update counter
				++closeFuncParenCtr;
				
				// check if closed all function parentheses
				if (openFuncParenCtr == closeFuncParenCtr) {
					
					// initialize counters
					openFuncParenCtr = 0;
					closeFuncParenCtr = 0;
				}
				
				// read next character
				continue;
			}
			
			// check if opened predicate parentheses
			if ( '[' == chars[i]) {
				
				// update counter
				++openPredicateParenCtr;
				
				// read next character
				continue;
			}
			
			// check if closed predicate parentheses
			if ( ']' == chars[i]) {
				
				// update counter
				++closePredicateParenCtr;
				
				// check if closed all predicate parentheses
				if (openPredicateParenCtr == closePredicateParenCtr) {
					
					// initialize counters
					openPredicateParenCtr = 0;
					closePredicateParenCtr = 0;
				}
				
				// read next character
				continue;
			}
			
			// check if read the delimiter
			if ( delimiter == chars[i]) {
				
				// check if not within parentheses
				if (0 != openFuncParenCtr || 0 != openPredicateParenCtr) {
					
					// the read delimiter is not free
					continue;
				}
				
				// split expression
				subExprs.add(expression.substring(currSubExprStart, i).trim()); // trim spaces before adding sub expression
				
				// next sub expression starts after the delimiter
				currSubExprStart = i + 1;
				
				// read next character
				continue;
			}
		}
		
		// add last sub expression
		subExprs.add(expression.substring(currSubExprStart, length).trim()); // add last sub expression and trim spaces
		
		// remove all empty strings
		while(subExprs.remove(""));
		
		// return sub expressions found
		return subExprs;
	}
	
	/**
	 * Gets condition and checks if after removing predicate parentheses
	 * and surrounding round parentheses, the condition is "last()"
	 * @param condition- condition to check
	 * @return True if after processing the condition is "last()",
	 * 		   False if not
	 */
	private boolean isConditionLast(String condition) {
		
		// check if condition is empty
		if (condition.equals("")) { return false; }
		
		// remove predicate parentheses
		condition = removeParentheses(condition, '[', ']');
		
		// remove surrounding round parentheses
		condition = removeParentheses(condition, '(', ')');
		
		// compare to "last()"
		return condition.equals("last()");
	}
	
	/**
	 * Gets condition and checks if after removing predicate parentheses
	 * and surrounding round parentheses, the condition is "not(last())"
	 * @param condition- condition to check
	 * @return True if after processing the condition is "not(last())",
	 * 		   False if not
	 */
	private boolean isConditionNegativeLast(String condition) {
		
		// check if condition is empty
		if (condition.equals("")) { return false; }
		
		// remove predicate parentheses
		condition = removeParentheses(condition, '[', ']');
		
		// remove surrounding round parentheses
		condition = removeParentheses(condition, '(', ')');
		
		// compare to "not(last())"
		return condition.equals("not(last())");
	}
	
	/**
	 * Composes path for node to be added. The path displays the position of
	 * the node among the other candidates and the path made so far
	 * @param candidatesValidations- validation for each candidate node, used
	 * 								  
	 * @param prevPath- path for source node of the evaluation that resulted
	 * 				    with the node to be added
	 * @param exprWithoutCondition- expression without condition
	 * @param nodeIndex- index of node to be added among the other candidates
	 * @param conditionValidation- validation for the condition
	 * @param numOfCandidates- how many candidate nodes there are
	 * @param usePrevPath- indicates if should use the path for source node
	 * @param source- source node for the evaluation
	 * @param nodeToAdd- node to be added
	 * @param addID- indicates if should extract parameter for id() in node's
	 * 				 path (if such parameter exists)
	 * @return path for the node be added
	 * @throws XPathExpressionException if had errors in evaluation parts of
	 * 					     	    	given expression
	 */
	private String composeNodePath(List<String> candidatesValidations,
			String prevPath, String exprWithoutCondition, int nodeIndex,
			String conditionValidation, int numOfCandidates,
			boolean usePrevPath, Node source, Node nodeToAdd, boolean addID)
			throws XPathExpressionException {
		
		// path to be composed
		String nodePath = "";
		
		// initialize parameter for "id()"
		String idParameter = "";
		
		// check if expression is "id(...)"
		if (addID && exprWithoutCondition.startsWith("id(")) {
			
			// check if there are any other segments
			List<String> segments = splitExpressions(exprWithoutCondition, '/');
			
			// extract id() parameter only when starts evaluating the condition
			if (segments.size() == 1) {				
				idParameter = "{" + extractIDParameter(exprWithoutCondition, source) + "}";
			}
		}
		
		// replace calls to "node()" and abbreviation of "*" with node-to-be-added's name
		exprWithoutCondition = writeNodeName(exprWithoutCondition, nodeToAdd);
				
        // check if composing path of first condition
        if (candidatesValidations.isEmpty()) {
        	
        	// compose index string
        	String index = "";
			if (numOfCandidates > 1) {
				index = "{" + (nodeIndex + 1) + "}";
			}
        	
        	// node's path should include previous path
			if (exprWithoutCondition.equals("")) {
				
				nodePath = prevPath + exprWithoutCondition + idParameter + index + conditionValidation;
				
			} else {
				
				// only at first time add id()'s parameter
				nodePath = prevPath
						+ exprWithoutCondition.substring(0, exprWithoutCondition.length() - 1)
						+ idParameter
						+ exprWithoutCondition.substring(exprWithoutCondition.length() - 1) 
						+ index + conditionValidation;
			} 
			
        } else { // use matching validation to compose the path 
        	
        	if (!usePrevPath) { 
        		prevPath = ""; 
        	} else {
        		// use path to source node and remove "/" at its end
        		prevPath = prevPath.substring(0, prevPath.length()-1);
        	}
        	
        	// composing path after validating successive condition
        	nodePath = prevPath + candidatesValidations.get(nodeIndex) + idParameter + conditionValidation;
        }	
		
        // return the composed path
		return nodePath;
	}
	
	/**
	 * Extracts condition from given expression:
	 * finds first "[" that are not between parentheses, and returns the rest
	 * of the expression.
	 * If given expression does not have any condition, returns an empty string 
	 * @param expression- expression that its conditions should be extracted
	 * @return condition extracted from expression
	 */
	private String extractCondition(String expression) {
		
		// convert expression string to array of chars
		char chars[] = expression.toCharArray();
		
		// get expression length
		int length = expression.length();
		
		// initialize counter for parentheses
		int roundParenCtr = 0;
		int predicateParenCtr = 0;
		
		// scan expression and search for predicate's beginning
		for (int i = 0 ; i < length ; ++i)
		{
			
			// count round parentheses
			if (chars[i] == '(') { ++roundParenCtr; continue; }
			if (chars[i] == ')') { --roundParenCtr; continue; }
			
			// count predicate parentheses
			if (chars[i] == ']') { --predicateParenCtr; continue; }
			
			// check if found predicate's beginning
			if (chars[i] == '[') {
				
				// check if parentheses are balanced
				if (roundParenCtr  == 0 && predicateParenCtr == 0) {
					
					// return expression's suffix
					return expression.substring(i, length);
				}
				
				// instance is not free
				++predicateParenCtr;
			}
				
		}
		
		// no condition found
		return "";
	}

	/**
	 * Gets condition and extracts the successive conditions.
	 * Successive conditions are: [condition_1][condition_2]...[condition_n].
	 * The sub-conditions are saved in a list
	 * @param condition- condition to be processed
	 * @return list of successive sub-conditions
	 */
	private List<String> extractSuccessiveConditions(String condition) {
		
		// allocate list to hold the sub-conditions
		List<String> succConditions = new LinkedList<String>();
		
		char[] chars = condition.toCharArray();
		int length = condition.length();
		int predicateParenCtr = 0; // counts instances of "[". incremented if read "[", decremented if read "]"
		int roundParenCtr = 0; // counts instances of "(". incremented if read "(", decremented if read ")"
		int currSubConditionStart = 0; // index of current sub-condition's start
		
		// scan condition and extract successive sub-conditions
		for (int i = 0 ; i < length ; ++i) {
 
			// count round parentheses
			if (chars[i] == '(') { ++roundParenCtr; continue; }
			if (chars[i] == ')') { --roundParenCtr; continue; }
			
			// count predicate parentheses
			if ('[' == chars[i]) { ++predicateParenCtr; continue; }
			if (']' == chars[i]) { --predicateParenCtr; }

			// check if completed reading a sub-condition out of round parentheses
			if (predicateParenCtr == 0 && roundParenCtr == 0) {
				
				// add current sub-condition to the list
				succConditions.add(condition.substring(currSubConditionStart, i+1));
				
				// get next sub-condition's start
				currSubConditionStart = i + 1;
			}
		}
		
		// return the conditions found
		return succConditions;
	}
	
	/**
	 * Validates condition that does not contain any free instance of
	 * a boolean operator (a free instance is an instance that is not
	 * between parentheses).
	 * If condition is a number or an arithmetic expression (can call
	 * to "position()" function), no validation is returned (returns
	 * an empty string)
	 * @param condition- condition to be validated
	 * @param source- source node to check the condition on
	 * @return if exists- validation for the boolean condition, otherwise- returns an empty string
	 */
	private String validateConditionNoBooleanOperator(String condition, Node source) {
		
		// check if given condition only specifies an index
		if (!condition.equals("") && !isNotSimpleIndexCondition(condition)) {
			
			// no need to validate
			return "";
		}		
		
		// remove predicate parentheses 
		condition = removeParentheses(condition, '[', ']');
		
		// check if should start evaluation from document root
		if (condition.charAt(0) == '/') { source = doc; }
		
		// initialize list to hold results
		XpathNodeListImplementation conditionResults = new XpathNodeListImplementation();
		
		try {
	
			// evaluate condition expression on each source node
			conditionResults.addNodeList((XpathNodeListImplementation)(evaluate(condition, source, XPathConstants.NODESET)));
		
			// check if source node fulfills the condition
			if (conditionResults.getLength() == 0) {
				
				// condition is not confirmed
				return "";
			}
			
			// remove first "/" from path to first node
			String path = conditionResults.getPathList().get(0).replaceFirst("/", "");
			
			// return validation
			return "[" + path + "]";
			
		} catch (Exception e) {
			
			// check if condition results in a numeric value			
			try {
				
				// evaluate condition expression and check if result is numeric
				double numericVal = (double) xpath.evaluate(condition, source, XPathConstants.NUMBER);
				
				// check if indeed a numeric value
				if (!Double.isNaN(numericVal)) {
					
					// result is numeric
					return "";
				}

			} catch (Exception error) { }

			// could not validate condition, and condition is not a numeric value, therefore no validation
			return "";
		}
	}

	/**
	 * Gets expression starting with id() and returns textual value of id()'s parameter
	 * @param idExpression- expression used to get the nodes using id()
	 * @param source- evaluation's source node
	 * @return textual value of content inside id(): 
	 * 		   if content is an explicit string, returns it,
	 * 		   otherwise, returns textual value of nodes resulting from
	 * 		   expression that is the parameter for id()
	 * @throws XPathExpressionException if had problems evaluating parameter for id()
	 */
	private String extractIDParameter(String idExpression, Node source) throws XPathExpressionException {
		
		// remove conditions from expression
		String expressionWithoutConditions = getExpressionWithoutCondition(idExpression);
		
		// get first segment
		List<String> segments = splitExpressions(expressionWithoutConditions, '/');
		
		// extract content inside "id()"
		String parameter = segments.get(0).substring("id(".length(), segments.get(0).length()-1);

		// check if id()'s parameter is an explicit string
		if (parameter.startsWith("\"")) { return parameter; }
		
		// get nodes resulting from evaluating id()'s parameter
		NodeList values = (NodeList) xpath.evaluate(parameter, source, XPathConstants.NODESET);
		
		// compose string holding textual value of nodes found
		int length = values.getLength();
		String result = "";
		for (int i = 0 ; i < length-1 ; ++i) {
			
			// add with spaces
			result = result + values.item(i).getTextContent() + " ";
		}
		
		// add last string
		result = result + values.item(length-1).getTextContent();
		
		// return result
		return "\"" + result + "\"";
	}

	/**
	 * Gets expression (without the condition part) that results in given node.
	 * If the last part of the expression calls to "node()" function or starts
	 * with "*", given node's name is written instead.
	 * If node's name is "#text", it is replaced with "text()", in order to match
	 * the path made to this node 
	 * @param exprWithoutCondition- expression to be processed
	 * @param nodeToAdd- node to be added to result list
	 * @return expression after processing, or original expression if no processing
	 * 		   was necessary
	 */
	private String writeNodeName(String exprWithoutCondition, Node nodeToAdd) {
		
		// replace nodes with the name "#text" by "text()"
		String nodeName = nodeToAdd.getNodeName();
		if (nodeName.startsWith("#text")) {
			nodeName = "text()";
		}

		// check if calls "node()" function
		if (exprWithoutCondition.endsWith("node()")) {
	
			// replace "node()" with current node name
			exprWithoutCondition = exprWithoutCondition.replaceFirst("node\\(\\)",nodeName);
		}
		
		// replace "*" with current node name
		if (exprWithoutCondition.startsWith("*")) {
			exprWithoutCondition = exprWithoutCondition.replaceFirst("\\*", nodeName);
		}
		
		// return processed expression
		return exprWithoutCondition;
	}
	
	/**
	 * Gets an expression and returns the part before the condition
	 * (book[...] -> book):
	 * Searches in given expression beginning of predicate ("[") that is not
	 * between round parentheses.
	 * If such is found, returns the prefix until the preciate's beginning.
	 * If not, returns the given expression
	 * @param expression- expression to process
	 * @return expression without conditions, or original expression if it
	 * 		   does not have any conditions
	 */
	private String getExpressionWithoutCondition(String expression) {

		// do nothing if expression is empty or is the condition
		if (!expression.equals("") && '[' == expression.charAt(0)) {
			return expression;
		}
		
		// convert expression string to array of chars
		char chars[] = expression.toCharArray();
		
		// initialize counter for round parentheses
		int roundParenCtr = 0;
		
		// get expression length
		int length = expression.length();
		
		// scan expression and search for predicate's beginning
		for (int i = 0 ; i < length ; ++i)
		{
			
			// count round parentheses
			if (chars[i] == '(') { ++roundParenCtr; continue; }
			if (chars[i] == ')') { --roundParenCtr; continue; }
			
			// check if found predicate's beginning out of round parentheses
			if (chars[i] == '[' && roundParenCtr == 0) {
				
				// return expression's prefix
				return expression.substring(0, i);
			}				
		}
		
		// no condition found
		return expression;
	}
	
	/**
	 * Checks if given condition (wrapped with predicate parentheses) is not 
	 * a simple index ("[5]")
	 * @param condition- condition to check
	 * @return True if condition is not a simple index, otherwise False
	 */
	private boolean isNotSimpleIndexCondition(String condition) {

		// check if empty expression
		if (condition.equals("")) {
			
			// empty expression does not contain any condition
			return false;
		}
		
		// remove parentheses
		String expresionWithoutParentheses = removeParentheses(condition, '[', ']');		
		
		// check if condition is a number
		try {
			
			Integer.parseInt(expresionWithoutParentheses);
			
		} catch (NumberFormatException e) {
			
			// condition is not a number
			return true;
		}
		
		// condition is a number
		return false;
	}

	/**
	 * Gets condition (wrapped with predicate parentheses) and checks if contains
	 * a numeric value. 
	 * Method should be called after could not validate condition- otherwise a
	 * condition such as "[price]" can result in a numeric value.
	 * A numeric value can be one of the following:
	 * 1. number
	 * 2. arithmetic expression (1+2*5+...)
	 * 3. arithmetic expression involving position() function (1+position()+...) 
	 * If so, returns condition's numeric value of the index condition. 
	 * Otherwise, returns NUMERIC_ERROR_VAL
	 * @param condition- condition to process
	 * @return condition's numeric value, or NUMERIC_ERROR_VAL if condition is not a numeric value
	 */
	private int getIndexCondition(String condition, int candidateIndex, Node candidateNode) {

		// check if empty string
		if (condition.equals("")) {
			
			// empty condition does not contain any number
			return NUMERIC_ERROR_VAL;
		}
		
		// remove predicate parentheses
		String conditionWithoutParentheses = removeParentheses(condition, '[', ']');

		// check if condition is a number
		int index = NUMERIC_ERROR_VAL;
		try {

			index = Integer.parseInt(conditionWithoutParentheses);
			
			// condition is a number
			return index;

		} catch (NumberFormatException e) { }

		
		// check if condition is an expression that results in a numeric value			
		try {
			
			// replace calls to "position()" referring to candidate node
			conditionWithoutParentheses = replacePositionWithValue(conditionWithoutParentheses, candidateIndex);
			
			// evaluate condition expression and check if result is numeric
			double numericVal = (double) xpath.evaluate(conditionWithoutParentheses, candidateNode, XPathConstants.NUMBER);
			
			// check if indeed a numeric value
			if (!Double.isNaN(numericVal)) {
				
				// result is numeric
				return (int) numericVal;
			}

			// condition is not numeric
			return NUMERIC_ERROR_VAL;
			
		} catch (Exception error) {
			
			// error in evaluation
			return NUMERIC_ERROR_VAL;
		}
	}
	
	/**
	 * Composes xpath expression in order to obtain the nodes that fulfill the condition
	 * @param prefix- prefix part before operator
	 * @param operator- first free operator
	 * @param postfix- postfix part before operator
	 * @param isNegative- indicates if condition is negative
	 * @param swapPrefixAndPostfix- indicates if should swap prefix and postfix in condition
	 * @return expression composed
	 */
	private String composeFulfillingNodesExpression(String prefix,
			String operator, String postfix, boolean isNegative,
			boolean swapPrefixAndPostfix) {
		
		// check if condition is negative
		String negativeStart = "";
		String negativeEnd = "";
		if (isNegative) {
			negativeStart = "not(";
			negativeEnd = ")";
		}
		
		// check if prefix is composed of segments
		List<String> prefixSegments = splitExpressions(prefix, '/');
		if (prefixSegments.size()>1) {
		
			// check if should check condition on #PCDATA of prefix
			if (prefix.endsWith("/text()")) {
				
				// swap prefix and postfix positions if necessary
				if (swapPrefixAndPostfix) {
					return composeExpression("self::node()/", prefix.substring(0, prefix.length()-"/text()".length()), 
							negativeStart+postfix, operator, "text()"+negativeEnd);
				}				
				
				return composeExpression("self::node()/", prefix.substring(0, prefix.length()-"/text()".length()), 
						negativeStart+"text()", operator, postfix+negativeEnd);
			}
			
			// check if condition applies on an attribute
			String lastSegment = prefixSegments.get(prefixSegments.size()-1); // get last segment
			
			// check if applies on an attribute value
			if (lastSegment.startsWith("@")) {
				
				// swap prefix and postfix positions if necessary
				if (swapPrefixAndPostfix) {
					return composeExpression("self::node()/", prefix.substring(0, prefix.length()-lastSegment.length()-"@".length()), 
							negativeStart+lastSegment, operator, postfix+negativeEnd);
				}
				
				return composeExpression("self::node()/", prefix.substring(0, prefix.length()-lastSegment.length()-"@".length()), 
						negativeStart+lastSegment, operator,  postfix+negativeEnd);
			}
		}

		// check if prefix is only "text()"
		if (prefix.equals("text()")) {
			
			// swap prefix and postfix positions if necessary
			if (swapPrefixAndPostfix) {
				return composeExpression("self::node()", negativeStart+postfix, operator, "text()"+negativeEnd);
			}
			
			return composeExpression("self::node()", negativeStart+"text()", operator, postfix+negativeEnd);
		}
		
		// check if prefix is only an attribute		
		if (prefix.startsWith("@")) {
			
			// swap prefix and postfix positions if necessary
			if (swapPrefixAndPostfix) {
				return composeExpression("self::node()", negativeStart+postfix, operator, prefix+negativeEnd);
			}
			
			return composeExpression("self::node()", negativeStart+prefix, operator, postfix+negativeEnd);
		}
		
		// check condition on a node
		if(swapPrefixAndPostfix) { // swap prefix and postfix positions if necessary
			return composeExpression("self::node()/", prefix, negativeStart+postfix, operator, "text()"+negativeEnd);
		}
		
		return composeExpression("self::node()/", prefix, negativeStart+"text()", operator, postfix+negativeEnd);
	}
	
	/**
	 * Returns xpath expression that is composed from given components.
	 * The expression composed considers a candidate node that should be checked
	 * if fulfills a certain condition
	 * @param firstPart- the part before the candidate node
	 * @param candidate- candidate node's name
	 * @param firstOperand- the part left to the operator
	 * @param operator- condition's operator
	 * @param secondOperand- the part right to the operator
	 * @return expression composed from given components
	 */
	private String composeExpression(String firstPart, String candidate,
			String firstOperand, String operator, String secondOperand) {
		
		// return composed expression
		return firstPart + candidate + "[" + firstOperand + operator + secondOperand + "]";
	}
	
	/**
	 * Returns xpath expression that is composed from given components.
	 * The expression composed does not considers a candidate node that should be checked 
	 * @param firstPart- the part before the candidate node
	 * @param firstOperand- the part left to the operator
	 * @param operator- condition's operator
	 * @param secondOperand- the part right to the operator
	 * @return expression composed from given components
	 */
	private String composeExpression(String firstPart, String firstOperand,
			String operator, String secondOperand) {
		
		// return composed expression
		return firstPart + "[" + firstOperand + operator + secondOperand + "]";
	}
	
	/**
	 * Gets expression that returns the candidate and checks if results
	 * in a node.
	 * If does not result in a node, returns True, otherwise False
	 * @param expressionForCandidate- expression to check
	 * @return True if does not result in a candidate, False if does
	 */
	private boolean notNodeCandidate(String expressionForCandidate) {
		
		return expressionForCandidate.endsWith("text()") 
				|| expressionForCandidate.startsWith("@");
	}
	
	/**
	 * Gets condition tokens list and replaces the axis abbreviations of
	 * "." and ".." with the actual axis: "self::node()" and "parent::node()".
	 * If tokens list is empty, does nothing
	 * @param conditionTokens- condition tokens to process
	 */
	private void replaceAxisAbrvInTokens(List<String> conditionTokens) {
		
		// check if could split to tokens
		if (conditionTokens.isEmpty()) {
			
			// nothing to be done			
			return;
		}
		
		// check if prefix token is "." or "." padded with spaces
		if (conditionTokens.get(PREFIX_INDX).trim().equals(".")) {
			
			// replace axis abbreviation
			replaceAxisAbrvInTokens(conditionTokens, PREFIX_INDX, ".", "self::node()");
			
		} else if (conditionTokens.get(PREFIX_INDX).trim().equals("..")) { // check if prefix token is ".." or ".." padded with spaces
			
			// replace axis abbreviation
			replaceAxisAbrvInTokens(conditionTokens, PREFIX_INDX, "..", "parent::node()");
		}
		
		// check if prefix token is "." or "." padded with spaces
		if (conditionTokens.get(POSTFIX_INDX).trim().equals(".")) {
			
			// replace axis abbreviation
			replaceAxisAbrvInTokens(conditionTokens, POSTFIX_INDX, ".", "self::node()");
			
		} else if (conditionTokens.get(POSTFIX_INDX).trim().equals("..")) { // check if prefix token is ".." or ".." padded with spaces
			
			// replace axis abbreviation
			replaceAxisAbrvInTokens(conditionTokens, POSTFIX_INDX, "..", "parent::node()");
		}
	}
	
	/**
	 * Gets condition tokens list and replaces in token of given index, 
	 * given axis abbreviation with given axis name
	 * @param conditionTokens- condition tokens to process
	 * @param index- condition 
	 * @param axisAbrv- axis abbreviation to be replaced
	 * @param axis- full axis name
	 */
	private void replaceAxisAbrvInTokens(List<String> conditionTokens, int index, String axisAbrv, String axis) {
		
		// get token at given index from list
		String token = conditionTokens.remove(index);
		
		// replace axis abbreviation in token
		token = token.replace(axisAbrv, axis);
				
		// add token back to list at its previous position
		conditionTokens.add(index, token);
	}
	
	/**
	 * Removes parentheses (of given type) from given expression until 
	 * no more can be removed (trims spaces first).
	 * If expression is not between parentheses, returns given expression
	 * @param expression- expression to process
	 * @param openParen- opening parentheses character
	 * @param closeParen- closing parentheses character
	 * @return expression after removing surrounding round parentheses
	 */
	private String removeParentheses(String expression, char openParen, char closeParen) {

		// trim spaces
		expression = expression.trim();
		
		String exprWithoutParentheses; // holds expression after trying removing parentheses
		
		// if is between parentheses, keep scanning given expression until parentheses are balanced
		while (expression.charAt(0) == openParen && expression.charAt(expression.length()-1) == closeParen) {
			
			// remove characters from both expression's ends
			exprWithoutParentheses = expression.substring(1, expression.length()-1);
			
			// check if parentheses are balanced
			if (isParenthesesValid(exprWithoutParentheses)) {
				
				// can remove characters safely
				expression = expression.substring(1, expression.length()-1);
			} else {
				
				// cannot remove round parentheses anymore
				return expression;
			}
		}
		
		// return processed expression
		return expression;
	}
	
	/**
	 * Gets expression and checks is parentheses in given expression
	 * are valid (balanced)
	 * @param expression- expression to check
	 * @return True if parentheses are valid, False if not
	 */
	private boolean isParenthesesValid(String expression) {
		
		// initialize counter for parentheses
		int roundParenCtr = 0;
		int predicateParenCtr = 0;
		
		// scan expression
		char[] chars = expression.toCharArray();
		int length = expression.length();
		for (int i = 0 ; i < length ; ++i) {
			
			// count round parentheses
			if (chars[i] == '(') { ++roundParenCtr; continue; }
			if (chars[i] == ')') { --roundParenCtr; continue; }
			
			// count predicate parentheses
			if (chars[i] == '[') { ++predicateParenCtr; continue; }
			if (chars[i] == ']') { --predicateParenCtr; continue; }
			
			// check if parentheses are not balanced in prefix
			if (roundParenCtr < 0 || predicateParenCtr < 0) { return false; }
		}
		
		// done scanning expression- check if parentheses are balanced
		if (roundParenCtr == 0 && predicateParenCtr == 0) {	return true; }
		
		// parentheses are not valid
		return false;
	}
	
	/**
	 * Checks if given condition is bounded within "not()"
	 * @param condition- condition to be checked
	 * @return True if condition is bounded within "not()", False if not
	 */
	private boolean isNegativeCondition(String condition) {

		// trim spaces
		condition = condition.trim();
		
		// check if condition is between "not()" and return result
		return condition.startsWith("not(") && condition.charAt(condition.length()-1) == ')';
	}

	/**
	 * If condition is a negative condition, removes the surrounding "not()".
	 * If condition is not negative, returns the condition
	 * @param condition- condition to be processed
	 * @return condition after removing the negation, or the condition if it is not negative
	 */
	private String removeNegationFromCondition(String condition) {

		// trim spaces
		condition = condition.trim();
		
		// check if condition is negative
		if (!isNegativeCondition(condition)) {
			
			// condition is not negative- nothing to be done
			return condition;
		}
		
		// remove surrounding "not()"
		return condition.substring("not(".length(), condition.length()-1);
	}	
	
	/**
	 * Replaces all instances of "position()" regarding candidate node, with candidate's
	 * index among other candidates
	 * @param condition- condition to be processed
	 * @param candidateIndex- index of candidate node among other candidates (counts from 1)
	 * @return condition after replacing "position()" with candidate node's position,
	 * 		   when position() calls are in context of candidate node
	 */
	private String replacePositionWithValue(String condition, int candidateIndex) {

		int newContextIndex = 0; // start index of expression that is evaluated at another context
		int substringToCheckStartIndex = 0; // start index of sub string to be checked in condition string
		boolean keepScanning = true; // indicates if should keep scanning condition
		
		// replace all instances of "position()" that are in context of candidate node
		while (keepScanning) {
			
			// get first instance of "count(" in remaining condition string
			newContextIndex = condition.substring(substringToCheckStartIndex, condition.length()).indexOf("count(");
			
			// if "count(" does not appear in remaining condition string, scan condition to the end
			if (newContextIndex == -1 || newContextIndex > condition.length()) { newContextIndex = condition.length(); }
						
			// replace "position()" with candidate node's position according to its context
			String newSubstring = condition.substring(substringToCheckStartIndex, newContextIndex).replace("position()", ""+candidateIndex);
			
			// backup condition's length before processing
			int prevLength = condition.length();
			
			// replace the substring in the condition
			condition = condition.substring(0, substringToCheckStartIndex) + newSubstring + condition.substring(newContextIndex);
			
			// find new context index after processing condition string
			newContextIndex = newContextIndex - (prevLength - condition.length()) + "ount".length()+1;
			
			// find where the "count()" expression ends
			int i = newContextIndex;
			for ( ; i < condition.length() ; ++i) {
				
				if (isParenthesesValid(condition.substring(newContextIndex, i + 1))) { break; }
			}
			substringToCheckStartIndex = i + 1;
			
			// check if should keep scanning condition
			keepScanning = (substringToCheckStartIndex < condition.length());
		}
		
		// return condition after processing
		return condition;
	}
	
	/**
	 * Checks if condition token at given index is between round parentheses.
	 * If so, removes the parentheses and returns True.
	 * Otherwise, does not change token and returns False
	 * @param conditionTokens- tokens of boolean condition
	 * @param index- index of token to be processed
	 * @return True if removed round parentheses from token, False if not
	 */
	private boolean processTokenParentheses(List<String> conditionTokens, int index) {
		
		// backup current token
		String tokenBackup = conditionTokens.get(index);
		
		// try removing parentheses from token
		removeRoundPrenthesesFromToken(conditionTokens, index);
		
		// is processed token has changed, then parentheses were removed
		return !(conditionTokens.get(index) == tokenBackup);
	}
	
	/**
	 * Removes round parentheses that bound condition token at given index
	 * @param conditionTokens- tokens of condition
	 * @param index- index of token to be processed
	 */
	private void removeRoundPrenthesesFromToken(List<String> conditionTokens, int index) {
		
		// get token from list
		String token = conditionTokens.remove(index);
		
		// remove parentheses from token
		token = removeParentheses(token, '(', ')');
		
		// add token back to list at its previous position
		conditionTokens.add(index, token);
	}
	
	/**
	 * Adds round parentheses to condition token at given index
	 * @param conditionTokens- tokens of condition
	 * @param index- index of token to be processed
	 */
	private void addRoundPrenthesesToToken(List<String> conditionTokens, int index) {
		
		// get token from list
		String token = conditionTokens.remove(index);
		
		// add parentheses to token
		token = "(" + token + ")";
		
		// add token back to list at its previous position
		conditionTokens.add(index, token);
	}
	
	/**
	 * Detects the delimiter operator and splits the given boolean condition
	 * according to this operator.
	 * An operator is a delimiter if there is a free instance of it.
	 * @param condition- condition to be split
	 * @return tokens after the split
	 */
	private List<String> splitBooleanConditionByOperator(String condition) {
		
		// initialize list to hold the tokens
		List<String> tokens = new LinkedList<String>();
				
		/* try splitting according to each operator.
		 * start with operators built of multiple characters 
		 */
		
		// try splitting by ">=" 
		tokens = splitBooleanConditionByString(condition, ">=");
		if (!tokens.isEmpty()) { return tokens; }
		
		// try splitting by "<=" 
		tokens = splitBooleanConditionByString(condition, "<=");
		if (!tokens.isEmpty()) { return tokens; }
		
		// try splitting by "!=" 
		tokens = splitBooleanConditionByString(condition, "!=");
		if (!tokens.isEmpty()) { return tokens; }
		
		// try splitting by ">" 
		tokens = splitBooleanConditionByString(condition, ">");
		if (!tokens.isEmpty()) { return tokens; }
		
		// try splitting by "<" 
		tokens = splitBooleanConditionByString(condition, "<");
		if (!tokens.isEmpty()) { return tokens; }
		
		// try splitting by "=" 
		tokens = splitBooleanConditionByString(condition, "=");
		if (!tokens.isEmpty()) { return tokens; }
		
		// could not split
		return tokens;
	}

	/**
	 * Splits given boolean condition to tokens, according to given delimiters.
	 * For example, if condition is "price>10", then the tokens are price, >, 10.
	 * More generally, the tokens are: prefix, delimiter, postfix. 
	 * The tokens are stored in the returned list, order is set by pre-defined indices:
	 * PREFIX_INDEX, OPERATOR_INDEX, POSTFIX_INDEX
	 * The operator token is given delimiter string's first instance that is not between parentheses
	 * @param condition- boolean condition to split
	 * @param delimiter- the delimiter that splits the prefix and postfix
	 * @return List of tokens
	 */
	private List<String> splitBooleanConditionByString(String condition, String delimiter) {

		// allocate token list
		List<String> conditionTokens = new LinkedList<String>();
		
		// check if no delimiter was given
		if (delimiter.equals("")) {
			
			// no splitting- the prefix is the entire condition
			conditionTokens.add(condition);
			conditionTokens.add("");
			conditionTokens.add("");
			return conditionTokens;
		}
		
		// scan the condition from left to write and find first free delimiter
		char[] chars = condition.toCharArray();
		int openFuncParenCtr = 0; // counts successive opening parentheses of a function- "(" 
		int openPredicateParenCtr = 0; // counts successive opening parentheses of a predicate- "["		
		int conditionLength = condition.length();
		for (int i = 0 ; i < conditionLength ; ++i) {

			// if read parentheses, update matching counter accordingly
			if ('(' == chars[i]) { ++openFuncParenCtr; continue; }
			if (')' == chars[i]) { --openFuncParenCtr; continue; }
			if ('[' == chars[i]) { ++openPredicateParenCtr; continue; }
			if (']' == chars[i]) { --openPredicateParenCtr; continue; }
			
			// check if starts reading a free instance of delimiter
			if ((0 == openFuncParenCtr) && (0 == openPredicateParenCtr)
					&& (delimiter.charAt(0) == chars[i] && (i > 0))) {
				
				// compare delimiter to current characters in condition
				boolean isMatch = true; // indicates if could match delimiter to condition's current substring
				int j = 0;
				for ( ; j < delimiter.length() ; ++j) {
					
					// compare current characters

					// check if exceeds string length
					if (i+j >= conditionLength) {
						
						// did not find match
						isMatch = false;						
						break;
					}

					// check if matching sequence is over
					if (delimiter.charAt(j) != chars[i+j]) {
						
						// current characters do not match
						isMatch = false;
						break;
					}
				}
				
				// check if found a free instance of delimiter
				if (isMatch) {

					// check if delimiter is not a substring
					if (delimiter.equals("and") || delimiter.equals("or")) {
						
						if (!((chars[i-1] == ')' || chars[i-1] == ']' || chars[i-1] == ' ') && (chars[i+j] == '(' || chars[i+j] == ' '))) {
							// instance found if a substring of another token, keep searching
							continue;
						}
					}
					
					// split condition at current position
					conditionTokens.add(PREFIX_INDX, condition.substring(0, i)); // add prefix
					conditionTokens.add(OPERATOR_INDX, condition.substring(i, i+j)); // add delimiter
					conditionTokens.add(POSTFIX_INDX, condition.substring(i+j, conditionLength)); // add postfix
					
					// trim spaces from each token					
					List<String> trimmedTokens = new ArrayList<String>(conditionTokens.size());
					for (String token : conditionTokens) {
						trimmedTokens.add(token.trim());
					}
					
					// return the trimmed tokens
					return trimmedTokens;
				}
			}
		}
		
		// no free instance found
		return conditionTokens;
	}
	
	/**
	 * Gets an expression and checks if expression is between round parentheses.
	 * If expression is between round parentheses, returns True. Otherwise, False
	 * @param expression- expression to be checked
	 * @return True if expression is between round parentheses, False if not
	 */
	private boolean isExprBetweenRoundParentheses(String expression) {
		
		// check if null or empty string is given
		if (expression == null || expression.equals("")) {
			
			// no need to check for parentheses
			return false;
		}
		
		// check start and end characters
		if (expression.charAt(0) == '(' && expression.charAt(expression.length()-1) == ')') {
			
			// expression is between round parentheses
			return true;
		}
		
		// expression is not between round parentheses
		return false;
	}
		
	/**
	 * Adds given postfix to each path on given list, and returns the result list  
	 * @param pathPostfix- postfix to add to each path
	 * @param paths- paths to be processed
	 * @return list of all processed paths
	 */
	private List<String> concatenatePaths(List<String> paths, String pathPostfix) {
		
		// initialize result list
		List<String> results = new LinkedList<String>();
		
		// add postfix to each path
		int length = paths.size();
		for (int i = 0 ; i < length ; ++i) {
			
			// get current path from given path list
			String currPath = paths.get(i);
			
			// add postfix
			currPath = currPath + pathPostfix;
			
			// add the processed path to result list
			results.add(currPath);
		}
		
		// return result list
		return results;
	}

}